﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace ProjectEulerIssues
{	
	partial class Program
	{
		static void Main(string[] args)
		{
			Problem117();
		}

		private static dynamic Problem251()
		{
			var PRIME_LIST = Misc.esieve(10000000);

			Func<Dictionary<long, long>, Dictionary<long, long>, Dictionary<long, long>> join = (Dictionary<long, long> s1, Dictionary<long, long> s2) =>
			{
				var s3 = new Dictionary<long, long>(s1);
				foreach (var s in s2)
				{
					if (!s3.ContainsKey(s.Key))
					{
						s3.Add(s.Key, s.Value);
					}
					else
					{
						s3[s.Key] += s.Value;
					}
				}
				return s3;
			};

			Func<Dictionary<long, long>, BigInteger> getNum = (Dictionary<long, long> num) =>
			{
				BigInteger ans = 1;
				foreach (var k in num)
				{
					ans *= BigInteger.Pow(k.Key, (int)k.Value);
				}
				return ans;
			};

			Action<Dictionary<long, long>, int, Dictionary<long, long>, HashSet<BigInteger>> calc = null;
			calc = (Dictionary<long, long> sn, int pos, Dictionary<long, long> b, HashSet<BigInteger> blist) =>
			{
				blist.Add(getNum(b));
				var keys = sn.Keys.ToArray();
				for (int i = pos; i < keys.Length; i++)
				{
					if (sn[keys[i]] >= 2)
					{
						var cn = sn[keys[i]] / 2;
						for (int j = 0; j < cn; j++)
						{
							sn[keys[i]] -= 2 * (j + 1);
							if (!b.ContainsKey(keys[i]))
							{
								b.Add(keys[i], 0);
							}
							b[keys[i]] += 2 * (j + 1);

							calc(sn, i + 1, b, blist);

							sn[keys[i]] += 2 * (j + 1);
							b[keys[i]] -= 2 * (j + 1);
						}
					}
				}
			};

			//const int LIMIT = 110000000;
			const int LIMIT = 1000000;

			Func<long> solve = () =>
			{
				Stopwatch sw = Stopwatch.StartNew();
				long count = 0;
				var blist = new HashSet<BigInteger>();
				for (long a = 2; a <= LIMIT; a += 3)
				{
					if (a % 10000 == 0)
					{
						Console.WriteLine("a: " + a);
					}
					var s1 = Misc.dissolve((a + 1) / 3, PRIME_LIST);
					var s2 = new Dictionary<long, long>(s1);
					var s3 = Misc.dissolve((8 * a - 1) / 3, PRIME_LIST);
					var sn = join(join(s1, s2), s3);
					var snLim = sn.Where(s => s.Value >= 2).ToDictionary(k => k.Key, k1 => k1.Value);
					blist.Clear();
					calc(snLim, 0, new Dictionary<long, long>() { { 1, 1 } }, blist);
					BigInteger bbc = getNum(sn);
					foreach (var bb in blist)
					{
						BigInteger c = bbc / bb;
						BigInteger b = bb.Sqrt();
						if ((BigInteger)a + b + c <= LIMIT)
						{
							count++;
						}
					}
				}
				sw.Stop();
				Console.WriteLine("Time: " + sw.ElapsedMilliseconds);
				return count;
			};
			return solve();
		}

		[SolutionInfo(Links = "http://mukeshiiitm.wordpress.com/2009/06/28/project-euler-200/")]
		private static dynamic Problem200()
		{
			const int LIMIT = 1000000;
			var prime_list = Misc.esieve(LIMIT);
			
			Func<BigInteger, bool> check = (BigInteger num) =>
			{
				var num_s = num.ToString();
				if (num_s.IndexOf("200") > -1)
				{
					bool isLastEven = int.Parse(num_s[num_s.Length - 1] + "") % 2 == 0;
					for (int i = (isLastEven ? num_s.Length - 1 : 0); i < num_s.Length; i++)
					{
						for (int j = 0; j < 10; j++)
						{
							if (i == 0 && j == 0)
							{
								continue;
							}
							if (num_s[i] + "" != j.ToString())
							{
								var newnum_s = num_s.Substring(0, i) + j.ToString() + (i + 1 < num_s.Length ? num_s.Substring(i + 1) : "");
								long newnum = long.Parse(newnum_s);
								if (Misc.isPrime(newnum, prime_list))
								{
									return false;
								}
							}
						}
					}
					return true;
				}
				return false;
			};

			Func<long> solve = () =>
			{
				var prProof200List = new List<BigInteger>();
				foreach (var p in prime_list)
				{
					foreach (var q in prime_list)
					{
						if (p == q)
						{
							break;
						}
						BigInteger num = BigInteger.Pow((BigInteger)p, 2) * BigInteger.Pow((BigInteger)q, 3);
						if (num.ToString().Length > 18)
						{
							break;
						}
						if (check(num))
						{
							prProof200List.Add(num);
							var num_s = num.ToString();
							Console.WriteLine(string.Format("{0}: {1} {2}", prProof200List.Count, num, (num_s.Length == 12 ? "!!!" : "")));

							if (num_s.Length == 12 && num_s.StartsWith("22") && num_s.EndsWith("2008"))
							{
								Console.WriteLine("YEAH: " + num_s);
							}
						}
					}
				}
				return (long)new SortedSet<BigInteger>(prProof200List).Skip(190).First();
			};
			return solve();
		}

		private static dynamic Problem145()
		{
			//10^9 - 1.000.000.000
			//half - 10^5

			Func<int, bool, int> getCount = (int num, bool oddLength) =>
			{
				int sum = 1;
				var num_s = num.ToString();
				for (int i = 0; i < num_s.Length; i++)
				{
					if (oddLength && i == num_s.Length - 1)
					{
						break;
					}
					int d = int.Parse(num_s[i] + "");
					if (d % 2 == 0)
					{
						sum *= 5;
					}
					else
					{
						sum *= (i == 0 ? 4 : 5);
					}
				}
				return sum;
			};

			Func<long> solve = () =>
			{
				long count = 0;
				for (int i = 1; i < 100000; i++)
				{
					count += getCount(i, true) + getCount(i, false);
				}
				return count;
			};

			HashSet<char> evenDigits = new HashSet<char> { '0', '2', '4', '6', '8' };

			Func<long, bool> isFit = (long num) =>
			{
				long numR = long.Parse(string.Join("", num.ToString().Reverse()));
				foreach (var c in (num + numR).ToString())
				{
					if (evenDigits.Contains(c))
					{
						return false;
					}
				}
				return true;
			};

			Func<long> solve2 = () =>
			{
				const long max = 1000000000;
				long count = 0;
				for (long i = 1; i < max; i++)
				{
					if (i % 10 != 0 && isFit(i))
					{
						count++;
					}
				}
				return count;
			};

			return solve2();
		}

		private static dynamic Problem135()
		{
			Func<object, Dictionary<long, int>> calculate = (object data) =>
			{
				var data_input = (Tuple<int, int>)data;
				const long limit = 1000000;
				var solutions = new Dictionary<long, int>();
				for (long x = data_input.Item1; x <= data_input.Item2; x++)
				{
					for (long d = x / 3 + 1; d > 0; d--)
					{
						if (x - 2 * d <= 0 || x - d <= 0)
						{
							break;
						}
						long nm = x * x - (x - d) * (x - d) - (x - 2 * d) * (x - 2 * d);
						if (nm <= 0)
						{
							break;
						}
						if (nm > limit)
						{
							continue;
						}
						if (!solutions.ContainsKey(nm))
							solutions.Add(nm, 1);
						else
							solutions[nm]++;
					}
				}
				return solutions;
			};

			Action<Dictionary<long, int>, Dictionary<long, int>> joinResults = (Dictionary<long, int> all, Dictionary<long, int> res) =>
			{
				foreach (var r2 in res)
				{
					if (!all.ContainsKey(r2.Key))
						all.Add(r2.Key, r2.Value);
					else
						all[r2.Key] += r2.Value;
				}
			};

			Func<long> solve4 = () =>
			{
				//(x + 2*d)^2 - (x+d)^2 - x^2 = n
				//x*x + 4*x*d + 4*d*d - x*x - 2*x*d - d*d - x*x = n
				//-x*x + 2*x*d + (3*d*d - n) = 0
				//x12 = (-2*d +-sqrt(4*d*d - 4*(-1)*(3*d*d-n))/(-2)
				//x12 = (-2*d +-sqrt(4*d*d + 4*(3*d*d-n))/(-2)
				//x12 = (-2*d +-sqrt(4*d*d + 12*d*d-4*n))/(-2)
				//x12 = (-2*d +-sqrt(16*d*d-4*n))/(-2)
				//x12 = (-2*d +-sqrt(4*d*d-n))/(-2)
				//4*d*d - n > 0
				//4*d*d > n
				//(4*d*d - n) = square

				const long limit = 1000000;
				var solutions = new int[limit + 1];
				for (long d = 1; d <= limit / 4 + 1; d++)
				{
					long d24 = 4 * d * d;
					long start = 0;
					if (d24 < limit)
					{
						start = 1;
						solutions[d24]++;
					}
					else
					{
						start = (long)Math.Sqrt(d24 - limit);
					}
					if (start < 1)
					{
						start = 1;
					}

					for (long root = start; root <= 2 * d; root++)
					{
						long n = d24 - root * root;
						if (n < 0)
						{
							break;
						}
						if (n < limit)
						{
							solutions[n]++;
							if (d > root)
							{
								solutions[n]++;
							}
						}
					}
				}
				long count = solutions.Where(c => c == 10).Count();
				return count;
			};

			Func<long> solve3_Parallel = () =>
			{
				const long limit = 1000000;

				var t1 = new Task<Dictionary<long, int>>(calculate, new Tuple<int, int>(3, 400000));
				var t2 = new Task<Dictionary<long, int>>(calculate, new Tuple<int, int>(400001, 600000));
				var t3 = new Task<Dictionary<long, int>>(calculate, new Tuple<int, int>(600001, 800000));
				var t4 = new Task<Dictionary<long, int>>(calculate, new Tuple<int, int>(800001, 1000000));
				Task.WaitAll(t1, t2, t3, t4);
				var all = new Dictionary<long, int>(t1.Result);
				joinResults(all, t2.Result);
				joinResults(all, t3.Result);
				joinResults(all, t4.Result);
				long sNum = all.Where(s => s.Key > 0 && s.Key < limit && s.Value == 10).Count();
				return sNum;
			};

			Func<long> solve2 = () =>
			{
				const long limit = 100000;
				var solutions = new Dictionary<long, int>();
				for (long x = 3; x <= limit; x++)
				{
					//(x-d)*(x-d) = x*x-d*x-d*x + d*d
					//x*x - (x*x - 2*d*x + d*d) - (x*x - 4*d*x + 4*d*d) > 0
					//-x*x + 5*d*x - 5*d*d > 0
					//-5*d*d + 5*d*x - x*x < limit
					//d1+d2 = x
					//d1*d2 = x*x/5
					//(-b+-sqrt(b*b-4*a*c))/2*a
					//d = (-5*x + sqrt(-25*x*x+20*x*x))

					for (long d = 1; d < x / 3 + 2; d++)
					{
						if (x + 2 * d >= limit || x + d >= limit)
						{
							break;
						}
						long nm = (x + 2 * d) * (x + 2 * d) - (x + d) * (x + d) - x * x;
						if (nm <= 0)
						{
							continue;
						}
						if (nm > limit)
						{
							break;
						}
						if (!solutions.ContainsKey(nm))
							solutions.Add(nm, 1);
						else
							solutions[nm]++;
					}
				}
				long sNum = solutions.Where(s => s.Key > 0 && s.Key < limit && s.Value == 10).Count();
				return sNum;
			};

			Func<long> solve = () =>
			{
				const int limit = 20000;
				var solutions = new Dictionary<long, int>();

				for (long x = 3; x <= limit; x++)
				{
					for (long y = x - 1; y > 0; y--)
					{
						for (long z = 1; z < y; z++)
						{
							long nm = x * x - y * y - z * z;
							if (nm < 0 || nm > limit)
							{
								break;
							}
							if (!solutions.ContainsKey(nm))
								solutions.Add(nm, 1);
							else
								solutions[nm]++;
						}
					}
				}
				long sNum = solutions.Where(s => s.Value == 10).Count();
				return sNum;
			};
			return solve4();
		}

		[SolutionInfo(Links = " http://freelancersunite.net/project_euler/project-euler-problem-131/ , http://wiki.san-ss.com.ar/project-euler-problem-131")]
		private static dynamic Problem131()
		{
			const int LIMIT = 1000000;

			Func<long> solve = () =>
			{
				//n^3 + n^2*p = x^3
				//n^2*(n+p) = x^3
				//n^2 and (n+p) are cubes!!!
				//(a+1)^3-a^3 = p
				var primes = Misc.esieve(LIMIT);
				var count = 0;
				for (int a = 1; a < 1000; a++)
				{
					int num = (int)(Math.Pow(a + 1, 3) - Math.Pow(a, 3));
					if (num >= LIMIT)
						break;
					if (primes.Contains(num))
						count++;
				}
				return count;
			};
			return solve();
		}

		[SolutionInfo(Links = "http://blog.dreamshire.com/2009/06/15/project-euler-problem-129-solution/")]
		private static dynamic Problem129()
		{
			const int MAX = 1000000;

			var primes = Misc.esieve(MAX + 1);

			Func<long, long> GetAn = (long n) =>
			{
				if (Misc.isPrime(n, primes) || Misc.gcd((int)n, 10) != 1)
					return 0;
				long x = 1, k = 1;
				while (x != 0)
				{
					x = (x * 10 + 1) % n;
					k++;
				}
				return k;
			};

			Func<long> solve = () => 
			{
				long n = MAX + 1;
				while (GetAn(n) < MAX + 1)
				{
					n += 2;
				}
				return n;
			};
			return solve();
		}

		private static dynamic Problem128()
		{
			const int MAX = 100000;
			var primes = Misc.esieve(MAX);

			Func<long, long[], bool> check = (long n, long[] near) => 
			{
				int pd = 0;
				foreach (var ne in near)
				{
					pd += Misc.isPrime(Math.Abs(n - ne), primes) ? 1 : 0;
				}
				return pd == 3;
			};

			Func<long> solve = () => 
			{
				var pdList = new List<long>() { 1, 2 };
				long step = 2;
				long num = 8;
				while (pdList.Count < 2000)
				{
					if (check(num, new long[] { num + step * 6, num + step * 6 + 1, num + step * 6 - 1, num + step * 6 + (step + 1) * 6 - 1 }))
					{
						pdList.Add(num);
					}
					if (check(num + step * 6 - 1, new long[] { num, num - 1, num - (step - 1) * 6, num + step * 6 + (step + 1) * 6 - 1, num + step * 6 + (step + 1) * 6 - 2 }))
					{
						pdList.Add(num + step * 6 - 1);
					}
					num += step * 6;
					step++;
				}
				return pdList[pdList.Count - 1];
			};
			return solve();
		}

		private static dynamic Problem127()
		{
			const int LIMIT = 120000;
			var primes = Misc.esieve(LIMIT);
			Dictionary<long, HashSet<long>> RAD = new Dictionary<long, HashSet<long>>();

			Func<long, HashSet<long>> getRad = (long x) =>
			{
				if (RAD.ContainsKey(x))
				{
					return RAD[x];
				}
				
				var pr = new HashSet<long>();
				RAD.Add(x, pr);
				if (primes.Contains(x))
				{
					pr.Add(x);
					return RAD[x];
				}
				long x1 = x;
				foreach (var p in primes)
				{
					if (x1 % p == 0)
					{
						pr.Add(p);
						x1 = x1 / p;
						while (x1 % p == 0)
						{
							x1 = x1 / p;
						}
					}
					if (x1 == 1)
					{
						break;
					}
				}
				return RAD[x];
			};

			Func<int, int, int, long> getRadMult = (int a, int b, int c) =>
			{
				long rd = 1;
				foreach (long r in getRad(a).Union(getRad(b)).Union(getRad(c)))
				{
					rd *= r;
				}
				return rd;
			};

			Func<int, long> getSingleRadMult = (int x) =>
			{
				long rd = 1;
				foreach (long r in getRad(x))
				{
					rd *= r;
				}
				return rd;
			};

			Func<long> solve = () =>
			{
				var watch = Stopwatch.StartNew();
				long sum = 0;
				long count = 0;
				for (int c = 3; c < LIMIT; c++)
				{
					if (getSingleRadMult(c) >= c)
					{
						continue;
					}
					for (int b = c - 1; b >= c / 2; b--)
					{
						int a = c - b;
						if (a >= b || Misc.gcd(a, b) != 1 || Misc.gcd(a, c) != 1 || Misc.gcd(b, c) != 1)
						{
							continue;
						}
						if (getRadMult(a, b, c) < c)
						{
							sum += c;
							count++;
						}
					}
				}
				watch.Stop();
				Console.WriteLine(watch.ElapsedMilliseconds);
				return sum;
			};
			return solve();
		}

		private static dynamic Problem125()
		{
			Func<long> solve2 = () =>
			{
				var nums = new HashSet<long>();
				for (int i = 1; i < 10000; i++)
				{
					long sum = i * i;
					for (int j = i + 1; j < 10000; j++)
					{
						sum += j * j;
						if (sum >= 100000000)
						{
							break;
						}
						if (string.Join("", sum.ToString().Reverse()) == sum.ToString())
						{
							nums.Add(sum);
						}
					}
				}
				long polSum = 0;
				foreach (var num in nums)
				{
					polSum += num;
				}
				return polSum;
			};

			Func<long> solve = () =>
			{
				var firstCache = new HashSet<long>();
				var cache = new HashSet<long>();
				long sum = 0;
				for (long i = 1; i <= 10000; i++)
				{
					long n = sum + i * i;
					firstCache.Add(n);
					if (string.Join("", n.ToString().Reverse()) == n.ToString())
					{
						cache.Add(n);
					}
					sum = n;
				}
				long subs = 0;
				for (long i = 1; i < 10000; i++)
				{
					subs += i * i;
					foreach (var f in firstCache)
					{
						long n = f - subs;
						if (n > 0 && !cache.Contains(n) && string.Join("", n.ToString().Reverse()) == n.ToString())
						{
							cache.Add(n);
						}
					}
				}
				long polSum = 0;
				foreach (var num in cache)
				{
					if (num < 100000000)
					{
						polSum += num;
					}
				}
				return polSum;
			};
			return solve2();
		}

		private static dynamic Problem124()
		{
			const int LIMIT = 100000;
			var primes = Misc.esieve(LIMIT);
			Dictionary<long, HashSet<long>> RAD = new Dictionary<long, HashSet<long>>();

			Func<long, HashSet<long>> getRad = (long x) =>
			{
				if (RAD.ContainsKey(x))
				{
					return RAD[x];
				}
				var pr = new HashSet<long>();
				RAD.Add(x, pr);
				if (primes.Contains(x))
				{
					pr.Add(x);
					return RAD[x];
				}
				long x1 = x;
				foreach (var p in primes)
				{
					if (x1 % p == 0)
					{
						pr.Add(p);
						x1 = x1 / p;
						while (x1 % p == 0)
						{
							x1 = x1 / p;
						}
					}
					if (x1 == 1)
					{
						break;
					}
				}
				return RAD[x];
			};

			Func<long, long> getRadProd = (long x) =>
			{
				long prod = 1;
				foreach (var num in getRad(x))
				{
					prod *= num;
				}
				return prod;
			};

			Func<long> solve = () =>
			{
				var eSet = new List<Tuple<long, long>>();
				for (long x = 1; x <= LIMIT; x++)
				{
					eSet.Add(new Tuple<long, long>(x, getRadProd(x)));
				}
				eSet.Sort((t1, t2) =>
				{
					if (t1.Item2 == t2.Item2)
						return t1.Item1 >= t2.Item1 ? 1 : -1;
					return (t1.Item2 >= t2.Item2 ? 1 : -1);
				});
				return eSet.ToArray()[10000 - 1].Item1;
			};
			return solve();
		}
		
		private static dynamic Problem123()
		{
			const int prime_limit = 1000000;
			var limit = Math.Pow(10, 10);
			var primes = Misc.esieve(prime_limit).ToArray();

			Func<long> solve = () =>
			{
				//(a-1)^n+(a+1)^n % a^2
				//if (n % 2 == 0) - remainder always be 2
				//(n % 2 == 1) - remainder have format 2*a*n
				int n = 7037;
				while (true)
				{
					long remainder = 2 * primes[n - 1] * n;
					if (remainder > limit && n % 2 == 1)
					{
						break;
					}
					n++;
				}
				return n;
			};
			return solve();
		}

		[SolutionInfo(Links = "Example implementations from http://en.wikipedia.org/wiki/Exponentiation_by_squaring (to calculate upper limit only), http://home.mnet-online.de/wzwz.de/temp/ebs/en.htm ")]
		private static dynamic Problem122()
		{
			int foundSteps = 0;
			
			Action<SortedSet<int>, int, int, int, int> findpath = null;
			findpath = (SortedSet<int> knownDigits, int step, int maxSteps, int currentNum, int num) => 
			{
				if (currentNum == num)
				{
					foundSteps = foundSteps == 0 ? step : Math.Min(foundSteps, step);
					return;
				}
				if (currentNum > num)
				{
					return;
				}
				if (num > 20 && step >= maxSteps)
				{
					return;
				}
				var hasNum = knownDigits.Contains(currentNum);
				knownDigits.Add(currentNum);
				var knownDigitsCopy = knownDigits.ToList();
				for (int i = knownDigitsCopy.Count - 1; i > -1; i--)
				{
					int newnum = currentNum + knownDigitsCopy[i];
					if (newnum > num)
					{
						continue;
					}
					findpath(knownDigits, step + 1, maxSteps, newnum, num);
				}
				if (!hasNum)
				{
					knownDigits.Remove(currentNum);
				}
			};

			Func<long> solve = () => 
			{
				var hash = new Dictionary<int, int>() { { 1, 0 }, { 2, 1 } };
				var sw = Stopwatch.StartNew();
				for (int i = 3; i <= 200; i++)
				{
					foundSteps = 0;
					int cnt = 0;
					int i2 = i;
					while (i2 > 1)
					{
						cnt += 1 + (i2 % 2);
						i2 /= 2;
					}
					cnt = (cnt > 11 ? 11 : cnt);
					findpath(new SortedSet<int>() { 1 }, 1, cnt, 2, i);
					Console.WriteLine(i + ": " + foundSteps);
					hash.Add(i, foundSteps);
				}
				sw.Stop();
				long sum = hash.Sum(kh => kh.Value);
				return sum;
			};
			return solve();
		}

		[SolutionInfo(Links = "http://keyzero.wordpress.com/2010/05/03/project-euler-problem-120/")]
		private static dynamic Problem120()
		{
			Func<long> solve = () => 
			{ 
				//(a-1)^n+(a+1)^n % a^2
				//if (n % 2 == 0) - remainder always be 2
				//(n % 2 == 1) - remainder have format 2*a*n
				//max remainder (2*a*n % a*a) will be when (n == (a-1)/2)
				long rMaxSum = 0;
				for (int a = 3; a <= 1000; a++)
				{
					int n = (a - 1) / 2;
					rMaxSum += 2 * a * n;
				}
				return rMaxSum;
			};
			return solve();
		}

		private static dynamic Problem119()
		{
			Func<BigInteger> solve = () => 
			{
				BigInteger limit = BigInteger.Pow(10, 14);
				var powhash = new SortedDictionary<BigInteger, Tuple<BigInteger, int>>();
				for (BigInteger d = 2; d < 100; d++)
				{
					BigInteger d2 = d;
					int pow = 1;
					while (d2 <= limit)
					{
						d2 *= d;
						pow++;
						var sumnum = d2.ToString().Select(c => BigInteger.Parse("" + c)).Sum();
						if (sumnum == d)
						{
							powhash.Add(d2, new Tuple<BigInteger, int>(d, pow));
						}
					}
				}
				return powhash.Keys.ToArray()[29];
			};
			return solve();
		}

		private static dynamic Problem118()
		{
			const int LIMIT = 1000000;
			HashSet<long> primes = Misc.esieve(LIMIT);
			var numHash = new HashSet<string>();

			Func<long, bool> isPrime = (long num) => 
			{
				if (num < LIMIT)
					return primes.Contains(num);
				foreach (var pr in primes)
				{
					if (pr > Math.Sqrt(num))
						return true;
					if (num % pr == 0)
						return false;
				}
				return true;
			};

			Action<List<int>, int, List<long>> makeSets = null;
			makeSets = (List<int> digits, int pos, List<long> nums) => 
			{
				long d = 0;
				for (int p = pos; p < digits.Count; p++)
				{
					d = d * 10 + digits[p];
					if (isPrime(d))
					{
						nums.Add(d);
						if (p == digits.Count - 1)
						{
							var nm = nums.ToList();
							nm.Sort();
							var nmHash = string.Join(",", nm);
							numHash.Add(nmHash);							
						}
						else
						{
							makeSets(digits, p + 1, nums);
						}
						nums.Remove(d);
					}
				}
			};

			Action<int, List<int>> generateSets = null;
			generateSets = (int pos, List<int> digits) => 
			{
				if (pos > 8)
				{
					//check last digit to be odd unless you can't get primes
					if (digits[digits.Count - 1] % 2 == 1)
					{
						makeSets(digits.ToList(), 0, new List<long>());
					}
				}
				else
				{
					for (int i = 1; i <= 9; i++)
					{
						if (!digits.Contains(i))
						{
							digits.Add(i);
							generateSets(pos + 1, digits);
							digits.Remove(i);
						}
					}
				}
			};

			Func<long> solve = () => 
			{
				var sw = Stopwatch.StartNew();
				generateSets(0, new List<int>());
				sw.Stop();
				return numHash.Count;
			};
			return solve();
		}

		private static dynamic Problem117()
		{
			const long LENGTH = 50;

			var cache = new Dictionary<long, long>();

			Func<long, long, long, long, long> search = null;
			search = (long start, long end, long minBrickLen, long maxBrickLen) =>
			{
				long count = 1;
				if (start >= end)
				{
					return count;
				}
				if (cache.ContainsKey(end - start))
				{
					return cache[end - start];
				}
				
				for (long brickLen = minBrickLen; brickLen <= maxBrickLen; brickLen++)
				{
					for (long pos = start; pos <= end - brickLen + 1; pos++)
					{
						count += search(pos + brickLen, end, minBrickLen, maxBrickLen);
					}
				}
				
				if (!cache.ContainsKey(end - start))
				{
					cache.Add(end - start, count);
				}
				return count;
			};

			Func<long, long> F3 = (long n) =>
			{
				cache.Clear();
				var count = search(1, n, 2, 4);
				return count;
			};

			Func<long> solve = () =>
			{
				long res = F3(LENGTH);
				return res;
			};
			return solve();
		}

		private static dynamic Problem116()
		{
			const long LENGTH = 50;
			
			long count = 0;
			Action<long, long, long> search = null;
			search = (long start, long end, long brickLen) =>
			{
				for (long pos = start; pos <= end; pos++)
				{
					if (brickLen <= (end - pos + 1))
					{
						count++;
						if (pos + brickLen <= end - brickLen + 1)
							search(pos + brickLen, end, brickLen);
					}
				}
			};

			Func<long, long, long> F2 = (long m, long n) =>
			{
				count = 0;
				search(1, n, m);
				return count;
			};

			Func<long> solve = () =>
			{
				long total = 0;
				for (int m = 2; m <= 4; m++)
				{
					total += F2(m, LENGTH);
				}
				return total;
			};
			return solve();
		}

		private static dynamic Problem115()
		{
			const long M = 50;
			const long LIMIT = 1000000;

			long count = 0;
			Action<long, long, long> search = null;
			search = (long start, long end, long minBrickLen) =>
			{
				for (long pos = start; pos <= end; pos++)
				{
					for (long brickLen = minBrickLen; brickLen <= (end - pos + 1); brickLen++)
					{
						count++;
						if (pos + brickLen + 1 <= end - minBrickLen + 1)
							search(pos + brickLen + 1, end, minBrickLen);
					}
				}
			};

			Func<long, long, long> F = (long m, long n) => 
			{
				count = 0;
				search(1, n, m);
				return count + 1;
			};

			Func<long> solve = () =>
			{
				long n = M + 1;
				while (F(M, n) < LIMIT)
				{
					n++;
				}
				return n;
			};
			return solve();
		}

		private static dynamic Problem114()
		{
			const long MIN_BRICK_LENGTH = 3;
			const long LENGTH = 50;
			long count = 0;

			Action<long, long> search = null;
			search = (long start, long end) =>
			{
				for (long pos = start; pos <= end; pos++)
				{
					for (long brickLen = MIN_BRICK_LENGTH; brickLen <= (end - pos + 1); brickLen++)
					{
						count++;
						if (pos + brickLen + 1 <= end - MIN_BRICK_LENGTH + 1)
							search(pos + brickLen + 1, end);
					}
				}
			};

			Func<long> solve = () => 
			{
				search(1, LENGTH);
				return count + 1;
			};
			return solve();
		}

		private static dynamic Problem113()
		{
			const int NumOfDigits = 100;
			long[,] incCount = new long[10, NumOfDigits + 1];
			long[,] decCount = new long[10, NumOfDigits + 1];

			Func<int, int, long> incNum = null;
			incNum = (int leftDigit, int numOfDigits) =>
			{
				if (incCount[leftDigit, numOfDigits] == 0)
				{
					if (numOfDigits == 1)
					{
						incCount[leftDigit, numOfDigits] = 10 - leftDigit;
					}
					else
					{
						for (int i = leftDigit; i < 10; i++)
						{
							incCount[leftDigit, numOfDigits] += incNum(i, numOfDigits - 1);
						}
					}
				}
				return incCount[leftDigit, numOfDigits];
			};

			Func<int, int, long> decNum = null;
			decNum = (int leftDigit, int numOfDigits) =>
			{
				if (decCount[leftDigit, numOfDigits] == 0)
				{
					if (numOfDigits == 1)
					{
						decCount[leftDigit, numOfDigits] = leftDigit + 1;
					}
					else
					{
						for (int i = leftDigit; i >= 0; i--)
						{
							decCount[leftDigit, numOfDigits] += decNum(i, numOfDigits - 1);
						}
					}
				}
				return decCount[leftDigit, numOfDigits];
			};

			Func<long> solve2 = () =>
			{
				long sum = 0;
				for (int i = 1; i <= NumOfDigits; i++)
				{
					sum += incNum(1, i) + decNum(9, i) - 10;
				}
				return sum;
			};
			return solve2();

			//99*98*97*...*91
			//123456789
			//1123456789
			//11123456789
			//1122345			
			//11223455
			long count = 0;

			Action<int, int, bool> search = null;
			search = (int d, int localcount, bool up) =>
			{
				if (localcount == 99)
				{
					count++;
				}
				else
				{
					if (up)
					{
						for (int i = d + 1; i < 10; i++)
						{
							for (int j = 0; j <= 99 - localcount; j++)
							{
								search(i, localcount + j, up);
							}
						}
					}
					else
					{
						for (int i = d - 1; i > -1; i--)
						{
							for (int j = 0; j <= 99 - localcount; j++)
							{
								search(i, localcount + j, up);
							}
						}
					}

				}
			};

			Func<long> solve = () =>
			{
				for (int i = 1; i < 10; i++)
				{
					for (int j = 1; j < 99; j++)
					{
						search(i, j, true);
						search(i, j, false);
					}
				}
				return count;
			};
			return solve();
		}

		private static dynamic Problem112()
		{
			Func<long, bool> isBounce = (long num) =>
			{
				var inc = false;
				var dec = false;
				var num_s = num.ToString();
				for (int i = 1; i < num_s.Length; i++)
				{
					var d1 = int.Parse(num_s[i - 1] + "");
					var d2 = int.Parse(num_s[i] + "");
					if (d1 == d2)
					{
						continue;
					}
					else if (d2 > d1)
					{
						inc = true;
					}
					else
					{
						dec = true;
					}
					if (inc && dec)
					{
						return true;
					}
				}
				return inc && dec;
			};

			Func<long> solve = () =>
			{
				long num = 0;
				long bounce = 0;
				while (true)
				{
					num++;
					if (isBounce(num))
					{
						bounce++;
					}
					if (bounce * 100 / num == 99 && bounce * 100 % num == 0)
					{
						break;
					}
				}
				return num;
			};
			return solve();
		}

		private static dynamic Problem111()
		{
			const int LIMIT_COUNT = 10;
			const long LIMIT_PRIMES = 1000000;

			HashSet<long> PRIMES = Misc.esieve((int)LIMIT_PRIMES);

			Action<int[], int, int, int, HashSet<long>> iterate = null;
			iterate = (int[] digits, int d, int start, int count, HashSet<long> found) =>
			{
				if (count == 0)
				{
					if (digits[0] != 0)
					{
						long num = Convert.ToInt64(string.Join("", digits));
						if (Misc.isPrime(num, PRIMES))
							found.Add(num);
					}
				}
				else
				{
					for (int i = start; i < digits.Length; i++)
					{
						if (digits[i] != d)
							continue;
						for (int j = 0; j < 10; j++)
						{
							if (j == d)
							{
								iterate(digits, d, i + 1, count, found);
							}
							else
							{
								digits[i] = j;
								iterate(digits, d, i + 1, count - 1, found);
								digits[i] = d;
							}
						}
					}
				}
			};

			Func<long> solve = () =>
			{
				long sumAll = 0;
				for (int i = 0; i < 10; i++)
				{
					var found = new HashSet<long>();
					for (int j = 1; j < LIMIT_COUNT; j++)
					{
						var digits = Enumerable.Repeat(i, LIMIT_COUNT).ToArray();
						found.Clear();
						iterate(digits, i, 0, j, found);
						if (found.Count > 0)
						{
							break;
						}
					}
					long sum = found.Sum();
					sumAll += sum;
				}
				return sumAll;
			};

			return solve();
		}

		[SolutionInfo(Links = "http://keyzero.wordpress.com/category/project-euler/project-euler-solutions-101-110/, https://sites.google.com/site/robertharamoto/Home/programming/project-euler-solutions/problems-0101-to-0200/problems-0101---0110/problem-0110")]
		private static dynamic Problem110()
		{
			const int PRIMES_LIMIT = 1000000;
			const long NUMBER_OF_VARIANTS = 4000000;
			var primes = Misc.esieve(PRIMES_LIMIT).ToArray();

			Func<Dictionary<long, long>, BigInteger> getNumber = (Dictionary<long, long> divs) => 
			{
				BigInteger res = 1;
				foreach (var dv in divs)
				{
					res *= (BigInteger)Math.Pow(dv.Key, dv.Value);
				}
				return res;
			};

			Func<Dictionary<long, long>, long> getNumberOfVariants = (Dictionary<long, long> divs) => 
			{
				long variants = 1;
				foreach (var dv in divs)
				{
					if (dv.Value == 0)
						continue;
					variants *= dv.Value * 2 + 1;
				}
				return variants / 2;
			};

			long nearistNumberOfVariants = NUMBER_OF_VARIANTS * 2;

			Action<Dictionary<long, long>, int> enumDivs = null;
			enumDivs = (Dictionary<long, long> divs, int pos) => 
			{
				var N = getNumber(divs);
				var variants = getNumberOfVariants(divs);
				if (variants > NUMBER_OF_VARIANTS && Math.Abs(variants - NUMBER_OF_VARIANTS) < Math.Abs(nearistNumberOfVariants - NUMBER_OF_VARIANTS))
				{
					nearistNumberOfVariants = variants;
					Console.WriteLine("N: " + N + ", Variants: " + nearistNumberOfVariants);
				}

				var keys = divs.Keys.ToArray();
				if (pos > keys.Length - 1)
					return;
				
				for (int i = 3; i >= 0; i--)
				{
					long old = divs[keys[pos]];
					divs[keys[pos]] = i;
					enumDivs(divs, pos + 1);
					divs[keys[pos]] = old;
				}
			};

			Func<long> solve = () => 
			{
				var divs = new Dictionary<long, long>();
				for (long i = 2; i < 50; i++)
				{
					if (primes.Contains(i))
					{
						divs.Add(i, 0);
					}
				}
				enumDivs(divs, 0);
				return nearistNumberOfVariants;
			};
			return solve();
		}

		[SolutionInfo(Links = "http://keyzero.wordpress.com/2010/06/05/project-euler-problem-108/")]
		private static dynamic Problem108()
		{
			const int solutionsLimit = 1000;

			var PRIME_LIST = Misc.esieve(100000);
			
			Func<long, long> solutions = (long n) =>				
			{
				var divs = Misc.dissolve(n, PRIME_LIST);

				long variants = 1;
				foreach (var dv in divs)
				{
					variants *= dv.Value * 2 + 1;
				}
				return variants / 2;
			};

			Func<long> solve = () =>
			{
				//y = n + (n*n / (x-n))
				//d = x - n
				long n = 30030;
				while (solutions(n) < solutionsLimit)
				{
					n++;
					if (n % 10000 == 0)
					{
						Console.WriteLine("n: " + n);
					}
				}
				return n;
			};
			return solve();
		}

		[SolutionInfo(Algorithm = "Алгоритм_Прима, http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9F%D1%80%D0%B8%D0%BC%D0%B0")]
		private static dynamic Problem107()
		{
			Func<int[][]> readNetwork = () =>
			{
				const string FILENAME = "network.txt";
				var data = File.ReadAllLines(FILENAME);
				var network = new List<int[]>();
				foreach (var line in data)
				{
					network.Add(line.Split(',').Select(c => (c == "-" ? 0 : int.Parse(c))).ToArray());
				}
				return network.ToArray();
			};

			Func<long> solve = () =>
			{
				var network = readNetwork();
				var used = new List<int>();
				used.Add(1);
				var free = new List<int>(Enumerable.Range(1, network.Length));
				var sumAll = 0;
				foreach (var f1 in free)
				{
					foreach (var f2 in free)
					{
						if (f2 > f1 && network[f1 - 1][f2 - 1] > 0)
						{
							sumAll += network[f1 - 1][f2 - 1];
						}
					}
				}
				free.Remove(1);
				var sum = 0;
				while (free.Count > 0)
				{
					var min = 0;
					var minF = 0;
					foreach (var f in free)
					{
						foreach (var u in used)
						{
							if (network[f - 1][u - 1] > 0)
							{
								if (network[f - 1][u - 1] < min || min == 0)
								{
									minF = f;
									min = network[f - 1][u - 1];
								}
							}
						}
					}
					if (min == 0)
					{
						//error
						break;
					}
					sum += min;
					used.Add(minF);
					free.Remove(minF);
				}
				return sumAll - sum;
			};
			return solve();
		}

		private static dynamic Problem105()
		{
			Func<long, int[], Tuple<long, long, List<int>>> getComb = (long varnum, int[] data) =>
			{
				int k = 0;
				List<int> listK = new List<int>();
				long sum = 0;
				long varnum_original = varnum;
				while (varnum > 0)
				{
					if (varnum % 2 == 1)
					{
						sum += data[k];
						listK.Add(k);
					}
					varnum /= 2;
					k++;
				}
				return new Tuple<long, long, List<int>>(varnum_original, sum, listK);
			};

			Func<string, Tuple<bool, long>> isSpecial = (string line) =>
			{
				var data = line.Split(',').Select(c => int.Parse(c)).ToArray();
				var varnumcache = new Dictionary<long, Tuple<long, long, List<int>>>();
				var sumcache = new Dictionary<long, List<Tuple<long, long, List<int>>>>();
				var countcache = new Dictionary<long, List<Tuple<long, long, List<int>>>>();
				var varnum = Math.Pow(2, data.Length);
				for (long i = 1; i < varnum; i++)
				{
					var ans = getComb(i, data);
					varnumcache.Add(i, ans);
					if (!countcache.ContainsKey(ans.Item3.Count))
					{
						countcache.Add(ans.Item3.Count, new List<Tuple<long, long, List<int>>>() { ans });
					}
					else
					{
						countcache[ans.Item3.Count].Add(ans);
					}
					if (!sumcache.ContainsKey(ans.Item2))
					{
						sumcache.Add(ans.Item2, new List<Tuple<long, long, List<int>>>() { ans });
					}
					else
					{
						foreach (var a in sumcache[ans.Item2])
						{
							if (a.Item3.Intersect(ans.Item3).Count() == 0)
							{
								return new Tuple<bool, long>(false, 0);
							}
						}
						sumcache[ans.Item2].Add(ans);
					}
				}

				foreach (var k1 in countcache)
				{
					foreach (var k2 in countcache)
					{
						if (k1.Key == k2.Key)
						{
							continue;
						}
						if (k1.Key < k2.Key)
						{
							break;
						}
						foreach (var k1a in k1.Value)
						{
							foreach (var k2a in k2.Value)
							{
								if (k1a.Item2 < k2a.Item2 && k1a.Item3.Intersect(k2a.Item3).Count() == 0)
								{
									return new Tuple<bool, long>(false, 0);
								}
							}
						}
					}
				}

				return new Tuple<bool, long>(true, data.Sum());
			};

			Func<long> solve = () =>
			{
				var data = File.ReadAllLines("sets.txt");
				long sum = 0;
				foreach (var line in data)
				{
					var ans = isSpecial(line);
					if (ans.Item1)
					{
						sum += ans.Item2;
					}
				}
				return sum;
			};
			return solve();
		}

		private static dynamic Problem104()
		{
			Func<string, bool> isFit = (string f) =>
			{
				if (f.Length < 9)
				{
					return false;
				}
				var digits = new HashSet<char>() { '0' };
				for (int i = 0; i < 9; i++)
				{
					if (digits.Contains(f[i]))
					{
						return false;
					}
					digits.Add(f[i]);
				}
				return true;
			};

			Func<string, bool> isFitInFirst = (string f) =>
			{
				if (f.Length < 9)
				{
					return false;
				}
				var digits = new HashSet<char>() { '0' };
				for (int i = f.Length - 1; i >= f.Length - 9; i--)
				{
					if (digits.Contains(f[i]))
					{
						return false;
					}
					digits.Add(f[i]);
				}
				return true;
			};

			Func<string, bool> isFitBoth = (string f) =>
			{
				if (f.Length < 9)
				{
					return false;
				}
				var digits = new HashSet<char>() { '0' };
				for (int i = 0; i < 9; i++)
				{
					if (digits.Contains(f[i]))
					{
						return false;
					}
					digits.Add(f[i]);
				}
				digits = new HashSet<char>() { '0' };
				for (int i = f.Length - 1; i >= f.Length - 9; i--)
				{
					if (digits.Contains(f[i]))
					{
						return false;
					}
					digits.Add(f[i]);
				}
				return true;
			};

			Func<string, string, bool, string> getNext = (string f1, string f2, bool cut10) =>
			{
				var res = new StringBuilder();
				int ost = 0;
				for (int i = 0; i < Math.Max(f1.Length, f2.Length); i++)
				{
					int d1 = i < f1.Length ? int.Parse(f1[i] + "") : 0;
					int d2 = i < f2.Length ? int.Parse(f2[i] + "") : 0;
					int dr = (d1 + d2 + ost) % 10;
					res.Append(dr);
					ost = (d1 + d2 + ost) / 10;
					if (cut10 && i == 10)
					{
						break;
					}
				}
				if (ost > 0)
				{
					res.Append(ost);
				}
				return res.ToString();
			};

			var fnCache = new Dictionary<int, string>() { { 1, "1" }, { 2, "1" } };

			Func<string, string, int, string> sumFib = (string fx, string fy, int shiftFy) =>
			{
				var res = new StringBuilder();
				shiftFy = (fx.Length >= shiftFy ? shiftFy : fx.Length);
				res.Append(fx.Substring(0, shiftFy));
				int ost = 0;
				for (int i = shiftFy; i < Math.Max(fx.Length, fy.Length); i++)
				{
					int d1 = i < fx.Length ? int.Parse(fx[i] + "") : 0;
					int d2 = i < fy.Length ? int.Parse(fy[i] + "") : 0;
					int dr = (d1 + d2 + ost) % 10;
					res.Append(dr);
					ost = (d1 + d2 + ost) / 10;
				}
				if (ost > 0)
				{
					res.Append(ost);
				}
				return res.ToString();
			};

			Func<string, string, string> prodFib = (string fx, string fy) =>
			{
				string resAll = "0";
				string beforeSpace = "";
				var prodLocalCache = new Dictionary<int, string>();
				for (int i = 0; i < fy.Length; i++)
				{
					int d1 = int.Parse(fy[i] + "");
					if (d1 != 0)
					//if (true)
					{
						var resStr = "";
						if (prodLocalCache.ContainsKey(d1))
						{
							resStr = prodLocalCache[d1];
						}
						else
						{
							var res = new StringBuilder();
							int ost = 0;
							for (int j = 0; j < fx.Length; j++)
							{
								int d2 = int.Parse(fx[j] + "");
								int dr = (d1 * d2 + ost) % 10;
								res.Append(dr);
								ost = (d1 * d2 + ost) / 10;
							}
							if (ost > 0)
							{
								res.Append(ost);
							}
							resStr = res.ToString();
							prodLocalCache.Add(d1, resStr);
						}
						resStr = beforeSpace + resStr;
						resAll = sumFib(resAll, resStr, beforeSpace.Length);
					}
					beforeSpace += "0";
				}
				return resAll;
			};

			var fnDictionary = new Dictionary<int, string>() { { 1, "1" }, { 2, "1" }, { 3, "2" } };
			var fnDictionaryProd = new Dictionary<int, string>(); //prod(fib1, fib1) cache
			var fnDictionaryProd2 = new Dictionary<int, string>(); //prod(fib1, 2) cache

			Func<int, string> findFib = null;
			findFib = (int k) =>
			{
				if (fnDictionary.ContainsKey(k))
				{
					return fnDictionary[k];
				}
				else if (k % 2 == 0)
				{
					int n = k / 2;
					string prod2 = null;
					if (fnDictionaryProd2.ContainsKey(n - 1))
					{
						prod2 = fnDictionaryProd2[n - 1];
					}
					else
					{
						prod2 = prodFib(findFib(n - 1), "2");
						fnDictionaryProd2.Add(n - 1, prod2);
					}
					string fk = prodFib(findFib(n), sumFib(prod2, findFib(n), 0));
					fnDictionary.Add(k, fk);
					return fk;
				}
				else
				{
					int n = k / 2 + 1;
					string prodNM = null;
					if (fnDictionaryProd.ContainsKey(n - 1))
					{
						prodNM = fnDictionaryProd[n - 1];
					}
					else
					{
						prodNM = prodFib(findFib(n - 1), findFib(n - 1));
						fnDictionaryProd.Add(n - 1, prodNM);
					}
					string prodN = null;
					if (fnDictionaryProd.ContainsKey(n))
					{
						prodN = fnDictionaryProd[n];
					}
					else
					{
						prodN = prodFib(findFib(n), findFib(n));
						fnDictionaryProd.Add(n, prodN);
					}
					string fk = sumFib(prodNM, prodN, 0);
					fnDictionary.Add(k, fk);
					return fk;
				}
			};

			decimal philog10 = decimal.Parse("0,2089876402499787");
			decimal sqrt5log10 = decimal.Parse("-0,349485002168009");
			string digitsStr = "123456789";

			Func<string, bool> PanDigital = (string num) =>
			{
				foreach (var digit in digitsStr)
				{
					if (!num.Contains(digit))
					{
						return false;
					}
				}
				return true;
			};

			Func<long, bool> CheckBottomDigits = (long check) =>
			{
				string num = check.ToString();
				if (num.Length >= 9)
				{
					if (PanDigital(num.Substring(num.Length - 9, 9)))
						return true;
				}
				return false;
			};

			Func<decimal, bool> CheckTopDigits = (decimal n) =>
			{
				decimal td = (n * philog10) + sqrt5log10;
				double t = Math.Pow(10, (double)(td - (int)td + 8));
				if (t.ToString().Length < 9)
					return false;
				if (PanDigital(t.ToString().Substring(0, 9)))
					return true;
				else
					return false;
			};

			Func<decimal> solve2 = () =>
			{
				long fnm2 = 1L;
				long fnm1 = 1L;
				long fn = 0L;
				decimal k = 2;
				bool found = false;

				while (!found)
				{
					k++;
					fn = fnm2 + fnm1;
					if (CheckBottomDigits(fn))
					{
						if (CheckTopDigits(k))
							found = true;
					}
					fnm2 = fnm1 % 1000000000;
					fnm1 = fn % 1000000000;

					if (k % 500 == 0)
						Console.WriteLine(k);
				}
				return k;
			};

			Func<long> solve = () =>
			{
				//F(2n-1) = F(n-1)^2 + F(n)^2
				//F(2n) = F(n)(2F(n-1)+F(n))
				const int LIMIT = 1000000;
				string f1 = "1";
				string f2 = "1";
				var candidates = new List<int>();
				for (int k = 3; k < LIMIT; k++)
				{
					string f3 = getNext(f1, f2, true);
					f1 = f2;
					f2 = f3;
					if (isFit(f2))
					{
						candidates.Add(k);
					}
				}
				int foundK = 0;
				var sw = Stopwatch.StartNew();
				foreach (var cand in candidates)
				{
					if (cand < 100000)
					{
						continue;
					}
					/*if (cand > 20000)
					{
						sw.Stop();
						Console.Write(sw.ElapsedMilliseconds); 
						//		sw.ElapsedMilliseconds	7195	long
						//		sw.ElapsedMilliseconds	6420	long
					}*/
					if (isFitBoth(findFib(cand)))
					{
						foundK = cand;
						break;
					}
				}
				return foundK;
			};
			return solve2();
		}

		[SolutionInfo(Algorithm = "http://luckytoilet.wordpress.com/tag/computational-geometry/")]
		private static dynamic Problem102()
		{
			// Slope of a line
			Func<double, double, double, double, double> slope = (double x1, double y1, double x2, double y2) =>
			{
				return (y1 - y2) / (x1 - x2);
			};

			// Y intercept given slope and point
			Func<double, double, double, double> yint = (double px, double py, double m) =>
			{
				return py - m * px;
			};

			// Determine if a line crosses the y axis
			Func<double, double, bool> cyax = (double ax, double bx) =>
			{
				if (ax < 0 && bx > 0) return true;
				if (bx < 0 && ax > 0) return true;
				return false;
			};

			// Contains origin, or not?
			Func<string, bool> cto = (string input) =>
			{
				var input_split = input.Split(',');
				double ax = double.Parse(input_split[0]);
				double ay = double.Parse(input_split[1]);
				double bx = double.Parse(input_split[2]);
				double by = double.Parse(input_split[3]);
				double cx = double.Parse(input_split[4]);
				double cy = double.Parse(input_split[5]);

				// Find slopes
				double mAB = slope(ax, ay, bx, by);
				double mBC = slope(bx, by, cx, cy);
				double mAC = slope(ax, ay, cx, cy);

				// Find y intercepts
				double yAB = yint(ax, ay, mAB);
				double yBC = yint(bx, by, mBC);
				double yAC = yint(cx, cy, mAC);

				// How many times it crosses the y intercept above 0
				int c = 0;

				if (yAB > 0 && cyax(ax, bx)) c++;
				if (yBC > 0 && cyax(bx, cx)) c++;
				if (yAC > 0 && cyax(ax, cx)) c++;

				return c == 1;
			};

			//easy one - from forum https://projecteuler.net/thread=102
			Func<string, bool> cto2 = (string input) =>
			{
				var input_split = input.Split(',');
				double ax = double.Parse(input_split[0]);
				double ay = double.Parse(input_split[1]);
				double bx = double.Parse(input_split[2]);
				double by = double.Parse(input_split[3]);
				double cx = double.Parse(input_split[4]);
				double cy = double.Parse(input_split[5]);

				var x1 = ((ax * by - ay * bx) >= 0);
				var x2 = ((bx * cy - by * cx) >= 0);
				var x3 = ((cx * ay - cy * ax) >= 0);
				return (x1 == x2 && x2 == x3);
			};

			Func<long> solve = () =>
			{
				var data = File.ReadAllLines("triangles.txt");
				long counter = 0;
				foreach (var line in data)
				{
					if (cto2(line))
					{
						counter++;
					}
				}
				return counter;
			};
			return solve();
		}

		private static dynamic Problem100()
		{
			//(k/n)*((n-k)/(n-1)) = 1/2
			//n > 1000000000000
			//(b/n)*((b-1)/(n-1)) = 1/2
			//Diophantine Quadratic Equation
			//2b^2 – 2b – n^2 + n = 0
			//2x^2 – y^2 – 2x + y = 0
			//Xn+1 = P*Xn + Q*Yn + K
			//Yn+1 = R*Xn + S*Yn + L
			//P = 3 Q = 2 K = -2 R = 4 S = 3 L = -3
			double limit = Math.Pow(10, 12);
			long b = 85;
			long n = 120;
			while (n < limit)
			{
				long b1 = 3 * b + 2 * n - 2;
				long n1 = 4 * b + 3 * n - 3;
				b = b1;
				n = n1;
			}
			return b;
		}

		private static dynamic Problem99()
		{
			var data = File.ReadAllLines("base_exp.txt");
			long a_max = 0;
			long b_max = 0;
			int line = 0;
			for (int i = 0; i < data.Length; i++)
			{
				long a = long.Parse(data[i].Split(',')[0]);
				long b = long.Parse(data[i].Split(',')[1]);
				if (line == 0)
				{
					a_max = a;
					b_max = b;
					line = i + 1;
				}
				else
				{
					if (b * Math.Log10(a) > b_max * Math.Log10(a_max))
					{
						a_max = a;
						b_max = b;
						line = i + 1;
					}
				}
			}
			return line;
		}

		private static dynamic Problem98()
		{
			Func<string, string, bool> isAnagram = (string w1, string w2) =>
			{
				if (w1 == string.Join("", w2.Reverse()))
				{
					return false;
				}
				if (w1 == w2)
				{
					return true;
				}
				if (w1.Length != w2.Length)
				{
					return false;
				}
				foreach (var c1 in w1)
				{
					if (!w2.Contains(c1))
					{
						return false;
					}
					w2 = w2.Remove(w2.IndexOf(c1), 1);
				}
				return true;
			};

			Func<string, long, Dictionary<char, char>, bool> isFit = (string w, long s, Dictionary<char, char> used) =>
			{
				var numS = s.ToString();
				if (numS.Length != w.Length)
				{
					return false;
				}
				for (int i = 0; i < w.Length; i++)
				{
					if (!used.ContainsKey(numS[i]))
					{
						used.Add(numS[i], w[i]);
					}
					else if (used[numS[i]] != w[i])
					{
						return false;
					}
				}
				foreach (var u in used)
				{
					foreach (var u2 in used)
					{
						if (u.Key == u2.Key)
						{
							continue;
						}
						if (u.Value == u2.Value)
						{
							return false;
						}
					}
				}
				return true;
			};

			Func<string, Dictionary<char, char>, long> getNum = (string w, Dictionary<char, char> used) =>
			{
				var s = "";
				for (int i = 0; i < w.Length; i++)
				{
					s += used.Where(u => u.Value == w[i]).First().Key;
				}
				return long.Parse(s);
			};

			Func<long> solve = () =>
			{
				var data = File.ReadAllText("words.txt");
				var words = data.Split(new string[] { "\",\"" }, StringSplitOptions.RemoveEmptyEntries);
				words[0] = words[0].Trim('"');
				words[words.Length - 1] = words[words.Length - 1].Trim('"');
				var squares = new Dictionary<long, int>();
				for (long i = 1; i < 1000000; i++)
				{
					squares.Add(i * i, (i * i).ToString().Length);
				}
				var ang = new Dictionary<string, HashSet<string>>();
				foreach (var word in words)
				{
					var isAdded = false;
					foreach (var angEl in ang.Keys)
					{
						if (isAnagram(angEl, word))
						{
							ang[angEl].Add(word);
							isAdded = true;
							break;
						}
					}
					if (!isAdded)
					{
						ang.Add(word, new HashSet<string>() { word });
					}
				}

				//var angS = ang.Where(a => a.Value.Count > 0).OrderBy(a => a.Key.Length).ToList()[0];
				//var sq3 = squares.Where(s => s.Value == 3).Select(s => s.Key);
				long max = 0;
				var maxS1 = "";
				var usedTest = new Dictionary<char, char>();
				isFit("FORMER", 613089, usedTest);
				//var angSTest = ang.Where(a => a.Value.Count > 1).ToList();
				foreach (var angS in ang.Where(a => a.Value.Count > 1))
				{
					foreach (var s in squares.Where(s => s.Value == angS.Key.Length).Select(s => s.Key))
					{
						foreach (var w1 in angS.Value)
						{
							var used = new Dictionary<char, char>();
							if (!isFit(w1, s, used))
							{
								continue;
							}
							foreach (var w in angS.Value)
							{
								if (w1 == w)
								{
									continue;
								}
								var num = getNum(w, used);
								if (num.ToString().Length != s.ToString().Length)
								{
									continue;
								}
								if (squares.ContainsKey(num))
								{
									if (max == 0 || s > max)
									{
										maxS1 = angS.Key;
										max = s;
									}
								}
							}
						}
					}
				}
				return max;
			};
			return solve();
		}

		private static dynamic Problem97()
		{
			long num = 2;
			for (int i = 2; i <= 7830457; i++)
			{
				num *= 2;
				if (num.ToString().Length > 10)
				{
					num = long.Parse(string.Join("", num.ToString().Reverse().Take(10).Reverse()));
				}
			}
			num = 28433 * num + 1;
			if (num.ToString().Length > 10)
			{
				num = long.Parse(string.Join("", num.ToString().Reverse().Take(10).Reverse()));
			}
			return num;
		}

		private static dynamic Problem96()
		{
			const int len = 9;
			int sum = 0;

			Func<int[][], int, int, List<int>> variants = (int[][] f, int x, int y) =>
			{
				var vrs = new List<int>(Enumerable.Range(1, 9));
				for (int k1 = 0; k1 < len; k1++)
				{
					vrs.Remove(f[x][k1]);
					vrs.Remove(f[k1][y]);
				}
				for (int k1 = (x / 3) * (len / 3); k1 < (x / 3) * (len / 3) + len / 3; k1++)
				{
					for (int k2 = (y / 3) * (len / 3); k2 < (y / 3) * (len / 3) + len / 3; k2++)
					{
						vrs.Remove(f[k1][k2]);
					}
				}
				return vrs;
			};

			Action<int[][], int> solve = null;
			solve = (int[][] f, int free) =>
			{
				if (free == 0)
				{
					sum += f[0][0] * 100 + f[0][1] * 10 + f[0][2];
					return;
				}
				var minList = new List<int>();
				int x = 0;
				int y = 0;
				for (int k1 = 0; k1 < len; k1++)
				{
					for (int k2 = 0; k2 < len; k2++)
					{
						if (f[k1][k2] != 0)
						{
							continue;
						}
						var v = variants(f, k1, k2);
						if (minList.Count == 0 || minList.Count > v.Count)
						{
							minList = v;
							x = k1;
							y = k2;
						}
					}
				}
				if (minList.Count == 0)
				{
					return;
				}
				foreach (var vr in minList)
				{
					f[x][y] = vr;
					solve(f, free - 1);
					f[x][y] = 0;
				}
			};

			Action main = () =>
			{
				var data = File.ReadAllLines("sudoku.txt");
				for (int i = 1; i < data.Length; i += len + 1)
				{
					var field = new int[len][];
					var free = 0;
					for (int j = i; j < i + len; j++)
					{
						field[j - i] = data[j].Select(c => int.Parse(c + "")).ToArray();
						free += field[j - i].Where(nm => nm == 0).Count();
					}
					if (free == 0)
					{
						continue;
					}
					solve(field, free);
				}
			};
			main();
			return sum;
		}

		[SolutionInfo(Links = "http://www.mathblog.dk/project-euler-93-longest-sequence/")]
		private static dynamic Problem93()
		{
			Func<double?, double?, int, double?> op = (double? d1, double? d2, int o) => 
			{
				if (d1 == null || d2 == null)
					return null;
				switch (o)
				{
					case 0: //+
						return d1 + d2;
					case 1: //-
						return d1 - d2;
					case 2: //*
						return d1 * d2;
					case 3: // /
						return (d2.Value == 0 ? null : d1 / d2);
				}
				return null;
			};

			Action<HashSet<int>, double?> insertNum = (HashSet<int> nums, double? num) => 
			{
				if (num == null)
					return;
				if (num.Value != (int)num.Value)
					return;
				nums.Add((int)num.Value);
			};

			Action<List<int>, HashSet<int>> fillNums = (List<int> digits, HashSet<int> nums) => 
			{
				for (int i = 0; i < 4; i++)
				{
					for (int j = 0; j < 4; j++)
					{
						for (int k = 0; k < 4; k++)
						{
							insertNum(nums, op(op(op(digits[0], digits[1], i), digits[2], j), digits[3], k));
							insertNum(nums, op(op(digits[0], op(digits[1], digits[2], j), i), digits[3], k));
							insertNum(nums, op(digits[0], op(op(digits[1], digits[2], j), digits[3], k), i));
							insertNum(nums, op(digits[0], op(digits[1], op(digits[2], digits[3], k), j), i));
							insertNum(nums, op(op(digits[0], digits[1], i), op(digits[2], digits[3], k), j));
						}
					}
				}
			};

			Action<List<int>, List<int>, HashSet<int>> calcPerm = null;
			calcPerm = (List<int> digits, List<int> usedDigits, HashSet<int> numbers) => 
			{
				if (usedDigits.Count == digits.Count)
				{
					fillNums(usedDigits, numbers);
				}
				else
				{
					foreach (var d in digits)
					{
						if (!usedDigits.Contains(d))
						{
							usedDigits.Add(d);
							calcPerm(digits, usedDigits, numbers);
							usedDigits.Remove(d);
						}
					}
				}
			};

			Func<List<int>, int> calc = (List<int> digits) => 
			{
				var numbers = new HashSet<int>();
				calcPerm(digits, new List<int>(), numbers);
				int len = 0;
				while (numbers.Contains(len + 1))
				{
					len++;
				}
				return len;
			};

			Func<long> solve = () => 
			{
				int maxlen = 1;
				string maxlennum = "0";
				for (int a = 1; a < 10; a++)
				{
					for (int b = a + 1; b < 10; b++)
					{
						for (int c = b + 1; c < 10; c++)
						{
							for (int d = c + 1; d < 10; d++)
							{
								int len = calc(new List<int>() { a, b, c, d });
								if (len > maxlen)
								{
									maxlen = len;
									maxlennum = a.ToString() + b.ToString() + c.ToString() + d.ToString();
								}
							}
						}
					}
				}
				return long.Parse(maxlennum);
			};
			return solve();
		}

		private static dynamic Problem92()
		{
			const int limit = 10000000;
			var iset = new HashSet<long>();
			for (long i = 2; i < limit; i++)
			{
				var isetLocal = new HashSet<long>();
				long newi = 0;
				while (newi != 1 && newi != 89)
				{
					if (newi == 0)
					{
						newi = i;
					}
					newi = newi.ToString().Select(d => { var d1 = long.Parse("" + d); return d1 * d1; }).Sum();
					if (iset.Contains(newi) || newi == 89)
					{
						iset.Add(i);
						foreach (var i2 in isetLocal)
						{
							iset.Add(i2);
						}
						break;
					}
					isetLocal.Add(newi);
				}
			}
			return iset.Count;
		}

		[SolutionInfo(Links = "http://www.mathblog.dk/project-euler-91-right-angle-triangles-quadrant/")]
		private static dynamic Problem91()
		{
			const int MAX = 50;

			Func<long> solve2 = () =>
			{
				int result = MAX * MAX * 3;
				for (int x = 1; x <= MAX; x++)
				{
					for (int y = 1; y <= MAX; y++)
					{
						int fact = (int)Misc.gcd(x, y);
						result += Math.Min(y * fact / x, (MAX - x) * fact / y) * 2;
					}
				}
				return result;
			};

			Func<long> solve = () =>
			{
				long sum = 3 * MAX * MAX;
				//sum += (MAX / 2) * 2;
				for (int x = 1; x <= MAX; x++)
				{
					for (int y = 1; y <= MAX; y++)
					{

					}
				}
				return sum;
			};
			return solve2();
		}

		private static dynamic Problem90()
		{
			List<int[]> cubes = new List<int[]>();

			Action<int, List<int>> generate = null;
			generate = (int start, List<int> nums) =>
			{
				if (nums.Count == 6)
				{
					cubes.Add(nums.ToArray());
				}
				else
				{
					for (int i = start; i <= 9; i++)
					{
						nums.Add(i);
						generate(i + 1, nums);
						nums.Remove(i);
					}
				}
			};

			var c1Need = new int[] { 0, 0, 0, 1, 2, 3, 4, 6, 8 };
			var c2Need = new int[] { 1, 4, 6, 6, 5, 6, 6, 4, 1 };

			Func<int[], int[], bool> check = (int[] c1, int[] c2) =>
			{
				if (c1.Intersect(c2).Count() == 6)
				{
					return false;
				}
				var c1ext = c1.Select(n => n == 9 ? 6 : n).ToArray();
				var c2ext = c2.Select(n => n == 9 ? 6 : n).ToArray();
				for (int i = 0; i < c1Need.Length; i++)
				{
					if (c1ext.Contains(c1Need[i]) && c2ext.Contains(c2Need[i]))
						continue;
					if (c1ext.Contains(c2Need[i]) && c2ext.Contains(c1Need[i]))
						continue;
					return false;
				}
				return true;
			};

			Func<long> solve = () =>
			{
				generate(0, new List<int>());

				long count = 0;
				for (int i = 0; i < cubes.Count; i++)
				{
					for (int j = i + 1; j < cubes.Count; j++)
					{
						if (check(cubes[i], cubes[j]))
						{
							count++;
						}
					}
				}
				return count;
			};
			return solve();
		}

		private static dynamic Problem89()
		{
			var romanHash = new Dictionary<string, int>() { 
				{ "M", 1000 }, {"CM" , 900},
				{ "D", 500 }, { "CD", 400 },
				{ "C", 100 }, { "XC" , 90},
				{ "L", 50 }, { "XL", 40 },
				{ "X", 10 }, { "IX", 9},
				{ "V", 5 }, { "IV", 4},
				{ "I", 1 } 
			};

			Func<string, int> getMinNumLength = (string s) =>
			{
				var num = 0;
				var s2 = s;
				while (s2.Length > 0)
				{
					foreach (var rom in romanHash.Keys)
					{
						if (s2.StartsWith(rom))
						{
							s2 = s2.Substring(rom.Length);
							num += romanHash[rom];
							break;
						}
					}
				}
				var small = new StringBuilder();
				var num2 = num;
				foreach (var rh in romanHash)
				{
					while (num2 >= rh.Value)
					{
						small.Append(rh.Key);
						num2 -= rh.Value;
					}
				}
				return small.Length;
			};

			Func<int> solve = () =>
			{
				var data = File.ReadAllLines("roman.txt");
				var origLenSum = 0;
				var lenSum = 0;
				foreach (var s in data)
				{
					origLenSum += s.Length;
					lenSum += getMinNumLength(s);
				}
				return origLenSum - lenSum;
			};
			return solve();
		}

		private static dynamic Problem87()
		{
			Func<long> solve = () =>
			{
				const int limit = 50000000;
				var primes = Misc.esieve((int)Math.Sqrt(limit)).ToList();
				var powers = new long[3][];
				var pr = new List<long>(primes);
				for (int k = 0; k < 3; k++)
				{
					for (int i = 0; i < primes.Count; i++)
					{
						pr[i] *= primes[i];
					}
					powers[k] = pr.ToArray();
				}

				var nums = new HashSet<long>();
				for (int i = 0; i < primes.Count; i++)
				{
					for (int i2 = 0; i2 < primes.Count; i2++)
					{
						for (int i3 = 0; i3 < primes.Count; i3++)
						{
							long num = powers[0][i] + powers[1][i2] + powers[2][i3];
							if (num > limit)
							{
								break;
							}
							nums.Add(num);
						}
					}
				}
				return nums.Count;
			};

			return solve();
		}

		private static dynamic Problem85()
		{
			const int limit = 2000;
			const int target = 2000000;
			int nearist = 0;
			int area = 0;
			Func<int, int, int> getRectCount = (int i, int j) =>
			{
				var count = 0;
				for (int k1 = 1; k1 <= i; k1++)
				{
					for (int k2 = 1; k2 <= j; k2++)
					{
						count += (i - k1 + 1) * (j - k2 + 1);
					}
				}
				return count;
			};

			Action solve = () =>
			{
				for (int i = 1; i < limit; i++)
				{
					for (int j = i; j < limit; j++)
					{
						var count = getRectCount(i, j);
						if (nearist == 0 || Math.Abs(count - target) < Math.Abs(nearist - target))
						{
							nearist = count;
							area = i * j;
						}
						if (count > target)
						{
							break;
						}
					}
				}
			};
			solve();
			return area;
		}

		[SolutionInfo(Algorithm = "A* (AStar), http://en.wikipedia.org/wiki/A*_search_algorithm, http://www.policyalmanac.org/games/aStarTutorial.htm, Dijkstra's algorithm, http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B")]
		private static dynamic Problem83()
		{
			const string FILENAME = "matrix83.txt";
			int[,] grid = null;

			Func<int> readInput = () =>
			{
				int lines = 0;
				string line;
				string[] linePieces;
				int minval = int.MaxValue;

				StreamReader r = new StreamReader(FILENAME);
				while (r.ReadLine() != null)
				{
					lines++;
				}

				grid = new int[lines, lines];
				r.BaseStream.Seek(0, SeekOrigin.Begin);

				int j = 0;
				while ((line = r.ReadLine()) != null)
				{
					linePieces = line.Split(',');
					for (int i = 0; i < linePieces.Length; i++)
					{
						grid[j, i] = int.Parse(linePieces[i]);
						minval = (minval > grid[j, i]) ? grid[j, i] : minval;
					}
					j++;
				}

				r.Close();
				return minval;
			};

			Func<long> solve = () =>
			{
				//init arrays
				int minval = readInput();
				int gridSize = grid.GetLength(0);
				int[,] g = new int[gridSize, gridSize];
				int[,] h = new int[gridSize, gridSize];
				int[,] searched = new int[gridSize, gridSize];

				SortedList<Tuple<int, int>, Tuple<int, int>> openList = new SortedList<Tuple<int, int>, Tuple<int, int>>();

				for (int i = 0; i < gridSize; i++)
				{
					for (int j = 0; j < gridSize; j++)
					{
						h[i, j] = minval * (2 * (gridSize - 1) + 1 - i - j);
						g[i, j] = int.MaxValue;
					}
				}

				//Add the start square
				g[0, 0] = grid[0, 0];
				openList.Add(new Tuple<int, int>(g[0, 0] + h[0, 0], 0), new Tuple<int, int>(0, 0));

				while (searched[gridSize - 1, gridSize - 1] < 2)
				{
					Tuple<int, int> current = openList.ElementAt(0).Value;
					openList.RemoveAt(0);
					int ci = current.Item1;
					int cj = current.Item2;
					searched[current.Item1, current.Item2] = 2;

					//Check the four adjacent squares
					for (int k = 0; k < 4; k++)
					{
						int cinew = 0;
						int cjnew = 0;

						switch (k)
						{
							case 0: //Check the square above
								cinew = ci - 1;
								cjnew = cj;
								break;
							case 1: //Check the square below
								cinew = ci + 1;
								cjnew = cj;
								break;
							case 2: //Check the square right
								cinew = ci;
								cjnew = cj + 1;
								break;
							case 3: //Check the square left
								cinew = ci;
								cjnew = cj - 1;
								break;
						}

						if (cinew >= 0 && cinew < gridSize &&
							cjnew >= 0 && cjnew < gridSize &&
							searched[cinew, cjnew] < 2)
						{
							if (g[cinew, cjnew] > g[ci, cj] + grid[cinew, cjnew])
							{
								g[cinew, cjnew] = g[ci, cj] + grid[cinew, cjnew];

								if (searched[cinew, cjnew] == 1)
								{
									int index = openList.IndexOfValue(new Tuple<int, int>(cinew, cjnew));
									openList.RemoveAt(index);
								}
								int l = 0;
								while (openList.ContainsKey(new Tuple<int, int>(g[cinew, cjnew] + h[cinew, cjnew], l))) l++;
								openList.Add(new Tuple<int, int>(g[cinew, cjnew] + h[cinew, cjnew], l), new Tuple<int, int>(cinew, cjnew));
								searched[cinew, cjnew] = 1;
							}
						}
					}
				}
				return g[gridSize - 1, gridSize - 1];
			};
			return solve();
		}

		[SolutionInfo(Links = "http://www.mathblog.dk/project-euler-82-find-the-minimal-path-sum-from-the-left-column-to-the-right-column/")]
		[DynamicProgrammingSolution]
		private static dynamic Problem82()
		{
			const string FILENAME = "matrix82.txt";

			Func<int[,]> readInput = () =>
			{
				int lines = 0;
				string line;
				string[] linePieces;

				StreamReader r = new StreamReader(FILENAME);
				while (r.ReadLine() != null)
				{
					lines++;
				}

				int[,] inputSquare = new int[lines, lines];
				r.BaseStream.Seek(0, SeekOrigin.Begin);

				int j = 0;
				while ((line = r.ReadLine()) != null)
				{
					linePieces = line.Split(',');
					for (int i = 0; i < linePieces.Length; i++)
					{
						inputSquare[j, i] = int.Parse(linePieces[i]);
					}
					j++;
				}

				r.Close();

				return inputSquare;
			};

			Func<long> solve = () =>
			{
				int[,] grid = readInput();

				int gridSize = grid.GetLength(0);
				int[] sol = new int[gridSize];

				//initialise solution
				for (int i = 0; i < gridSize; i++)
				{
					sol[i] = grid[i, gridSize - 1];
				}

				for (int i = gridSize - 2; i >= 0; i--)
				{
					// Traverse down
					sol[0] += grid[0, i];

					for (int j = 1; j < gridSize; j++)
					{
						sol[j] = Math.Min(sol[j - 1] + grid[j, i], sol[j] + grid[j, i]);
					}

					//Traverse up
					for (int j = gridSize - 2; j >= 0; j--)
					{
						sol[j] = Math.Min(sol[j], sol[j + 1] + grid[j, i]);
					}
				}
				return sol.Min();
			};
			return solve();
		}

		private static dynamic Problem81()
		{
			//const int size = 5;
			//string[] data = File.ReadAllLines("matrix2.txt");

			const int size = 80;
			string[] data = File.ReadAllLines("matrix.txt");

			var d = data.Select(l => l.Split(',').Select(m => long.Parse(m)).ToArray()).ToArray();
			for (int i = 0; i < size; i++)
			{
				for (int j = 0; j < size; j++)
				{
					if (i == 0 && j == 0)
					{
						continue;
					}
					long num1 = (i - 1 >= 0 ? d[i - 1][j] : 0);
					long num2 = (j - 1 >= 0 ? d[i][j - 1] : 0);
					if (num1 == 0)
					{
						d[i][j] += num2;
					}
					else if (num2 == 0)
					{
						d[i][j] += num1;
					}
					else if (num1 > num2)
					{
						d[i][j] += num2;
					}
					else
					{
						d[i][j] += num1;
					}
				}
			}
			return d[size - 1][size - 1];
		}

		private static dynamic Problem80()
		{
			Func<int, int, BigInteger> Squareroot = (int n, int digits) =>
			{
				BigInteger limit = BigInteger.Pow(10, digits + 1);
				BigInteger a = 5 * n;
				BigInteger b = 5;

				while (b < limit)
				{
					if (a >= b)
					{
						a -= b;
						b += 10;
					}
					else
					{
						a *= 100;
						b = (b / 10) * 100 + 5;
					}
				}

				return b / 100;
			};

			Func<BigInteger, int> DigitSum = (BigInteger number) =>
			{
				char[] k = number.ToString().ToCharArray();
				int ds = 0;

				for (int i = 0; i < k.Length; i++)
				{
					ds += k[i] - '0';
				}

				return ds;
			};

			int result = 0;
			int j = 1;

			for (int i = 1; i <= 100; i++)
			{
				if (j * j == i)
				{
					j++;
					continue;
				}
				result += DigitSum(Squareroot(i, 100));
			}

			return result;
		}

		private static dynamic Problem79()
		{
			#region keys
			var keys = @"319
680
180
690
129
620
762
689
762
318
368
710
720
710
629
168
160
689
716
731
736
729
316
729
729
710
769
290
719
680
318
389
162
289
162
718
729
319
790
680
890
362
319
760
316
729
380
319
728
716";
			#endregion

			var keys_array = keys.Split(new string[] { "\r\n" }, StringSplitOptions.None).Select(key => int.Parse(key));
			var first_array = new List<int>();
			var linked = new Dictionary<int, List<int>>();
			var unique = new List<int>();
			foreach (var k in keys_array)
			{
				var k1 = k % 10;
				var k2 = (k / 10) % 10;
				var k3 = k / 100;

				if (!unique.Contains(k1))
				{
					unique.Add(k1);
				}
				if (!unique.Contains(k2))
				{
					unique.Add(k2);
				}
				if (!unique.Contains(k3))
				{
					unique.Add(k3);
				}

				if (!first_array.Contains(k1))
				{
					first_array.Add(k1);
				}
				first_array.Remove(k2);
				first_array.Remove(k3);

				if (!linked.ContainsKey(k1))
				{
					linked.Add(k1, new List<int>());
				}
				if (!linked[k1].Contains(k2))
				{
					linked[k1].Add(k2);
				}

				if (!linked.ContainsKey(k2))
				{
					linked.Add(k2, new List<int>());
				}
				if (!linked[k2].Contains(k3))
				{
					linked[k2].Add(k3);
				}
			}

			var minlen = 0;
			var min = 0;

			Action<int, List<int>> search = null;
			search = (int digit, List<int> used) =>
			{
				if (used.Contains(digit))
				{
					return;
				}
				used.Insert(0, digit);
				if (used.Count == unique.Count)
				{
					var num = string.Join("", used.Select(u => u.ToString()));
					if (minlen == 0 || num.Length < minlen)
					{
						minlen = num.Length;
						min = int.Parse(num);
					}
				}
				else if (used.Count < unique.Count && linked.ContainsKey(digit))
				{
					foreach (var digit_link in linked[digit])
					{
						search(digit_link, used);
						used.Remove(digit_link);
					}
				}
			};

			foreach (var first in first_array)
			{
				search(first, new List<int>());
			}

			return null;
		}

		private static dynamic Problem78()
		{
			List<int> p = new List<int>();
			p.Add(1);

			int n = 1;
			while (true)
			{
				int i = 0;
				int penta = 1;
				p.Add(0);

				while (penta <= n)
				{
					int sign = (i % 4 > 1) ? -1 : 1;
					p[n] += sign * p[n - penta];
					p[n] %= 1000000;
					i++;

					int j = (i % 2 == 0) ? i / 2 + 1 : -(i / 2 + 1);
					penta = j * (3 * j - 1) / 2;
				}

				if (p[n] == 0) break;
				n++;
			}
			return n;
		}

		[DynamicProgrammingSolution]
		private static dynamic Problem77()
		{
			const long LIMIT_PRIMES = 1000000;

			Func<long> solve = () =>
			{
				var primesList = Misc.esieve((int)LIMIT_PRIMES).ToArray();
				int target = 2;
				while (true)
				{
					int[] ways = new int[target + 1];
					ways[0] = 1;
					for (long i = 0; i < primesList.Length; i++)
					{
						for (long j = primesList[i]; j <= target; j++)
						{
							ways[j] += ways[j - primesList[i]];
						}
					}
					if (ways[target] > 5000)
					{
						break;
					}
					target++;
				}
				return target;
			};
			return solve();
		}

		[DynamicProgrammingSolution]
		private static dynamic Problem76()
		{
			int target = 100;
			int[] ways = new int[target + 1];
			ways[0] = 1;

			for (int i = 1; i <= 99; i++)
			{
				for (int j = i; j <= target; j++)
				{
					ways[j] += ways[j - i];
				}
			}
			return ways[target];
		}

		private static dynamic Problem75()
		{
			const int limit = 1500000;
			var low_limit = (int)Math.Sqrt(limit);
			var sums = new Dictionary<int, int>();
			for (int m = 2; m <= low_limit; m += 2)
			{
				for (int n = 1; n <= low_limit - m; n += 2)
				{
					if (Misc.gcd(m, n) == 1)
					{
						var sum = Math.Abs(n * n - m * m) + 2 * m * n + m * m + n * n;
						for (int sm = sum; sm <= limit; sm += sum)
						{
							if (!sums.ContainsKey(sm))
							{
								sums.Add(sm, 0);
							}
							sums[sm]++;
						}
					}
				}
			}
			var sumsOneCount = sums.Count(sm => { return (sm.Value == 1 && sm.Key <= limit); });
			return sumsOneCount;
		}

		[UniqueSolution]
		private static dynamic Problem74()
		{
			Stopwatch clock = Stopwatch.StartNew();

			var fact = new Dictionary<int, long>();
			fact[0] = 1;
			fact[1] = 1;
			long fc = 1;
			for (int i = 2; i < 10; i++)
			{
				fc *= i;
				fact[i] = fc;
			}

			Func<long, long> getNext = (long num) =>
			{
				return num.ToString().Select(c => { return fact[int.Parse(c + "")]; }).Sum();
			};

			var cycleHash = new Dictionary<long, int>();

			var res = 0;
			for (int i = 3; i < 1000000; i++)
			{
				var hash = new HashSet<long>();
				hash.Add(i);
				int count = 1;
				long prev = i;
				long next = getNext(prev);
				hash.Add(next);
				while (next != i)
				{
					long next1 = getNext(next);
					prev = next;
					next = next1;
					if (cycleHash.ContainsKey(next))
					{
						count += cycleHash[next];
						break;
					}
					if (hash.Contains(next) && next != i)
					{
						if (!cycleHash.ContainsKey(next))
						{
							var c = 0;
							foreach (var h in hash)
							{
								if (h == next)
								{
									c++;
								}
								else if (c != 0)
								{
									c++;
								}
							}
							cycleHash.Add(next, c);
						}
						break;
					}
					hash.Add(next);
					count++;
				}
				if (count + 1 == 60)
				{
					res++;
				}
			}

			clock.Stop();
			Console.WriteLine(clock.Elapsed.TotalMilliseconds);

			return res;
		}

		private static dynamic Problem73()
		{
			//Farey sequence
			//next after 1/3 is 4000/11999. a/b and c/d, and c/d after a/b if b*c-a*d=1
			int limit = 12000;
			int a = 1;
			int b = 3;
			int c = 4000;
			int d = 11999;

			int result = 0;

			while (!(c == 1 && d == 2))
			{
				result++;
				int k = (limit + b) / d;
				int e = k * c - a;
				int f = k * d - b;
				a = c;
				b = d;
				c = e;
				d = f;
			}
			return result;
		}

		private static dynamic Problem72()
		{
			const int limit = 1000000;
			int[] phi = Enumerable.Range(0, limit + 1).ToArray();
			long result = 0;
			for (int i = 2; i <= limit; i++)
			{
				if (phi[i] == i)
				{
					for (int i2 = i; i2 <= limit; i2 += i)
					{
						phi[i2] = phi[i2] / i * (i - 1);
					}
				}
				result += phi[i];
			}
			return result;
		}

		private static dynamic Problem71()
		{
			//p/q < a/b
			//r/s < p/q
			long a = 3;
			long b = 7;
			long r = 0;
			long s = 1;
			int limit = 1000000;

			for (int q = limit; q > 2; q--)
			{
				long p = (a * q - 1) / b;
				if (p * s > r * q)
				{
					s = q;
					r = p;
				}
			}
			return r;
		}

		private static dynamic Problem70()
		{
			const int limit = 10000000;

			HashSet<long> primes = Misc.esieve(limit);

			Func<long, long> totient = (long num) =>
			{
				if (num == 1)
				{
					return 1;
				}
				long nom = 1;
				long den = 1;
				foreach (var k in primes)
				{
					//if (k > Math.Sqrt(num))
					if (k > num / 2)
					{
						break;
					}
					if (num % k == 0)
					{
						nom *= (k - 1);
						den *= k;
					}
				}
				return num / den * nom;
			};

			Func<long, long, bool> isPerm = (long num, long tot) =>
			{
				var s1 = num.ToString();
				var s2 = tot.ToString();
				bool perm = true;
				foreach (var c1 in s1)
				{
					if (!s2.Contains(c1))
					{
						perm = false;
						break;
					}
					s2 = s2.Remove(s2.IndexOf(c1), 1);
				}
				return perm;
			};

			double min = 0;
			long n = 0;
			for (long i = 2; i < 10000000; i++)
			{
				if (primes.Contains(i))
				{
					continue;
				}
				long t = totient(i);
				if (isPerm(i, t))
				{
					if (min == 0 || (double)i / (double)t < min)
					{
						min = (double)i / (double)t;
						n = i;
					}
				}
			}
			return n;
		}

		private static dynamic Problem69()
		{
			const int limit = 1000000;
			
			var primes_list = Misc.esieve(limit).ToArray();
			long result = 1;
			int i3 = 0;
			while (result * primes_list[i3] < limit)
			{
				result *= primes_list[i3];
				i3++;
			}
			return result;
		}

		private static dynamic Problem67()
		{
			#region data
			var data = @"59
73 41
52 40 09
26 53 06 34
10 51 87 86 81
61 95 66 57 25 68
90 81 80 38 92 67 73
30 28 51 76 81 18 75 44
84 14 95 87 62 81 17 78 58
21 46 71 58 02 79 62 39 31 09
56 34 35 53 78 31 81 18 90 93 15
78 53 04 21 84 93 32 13 97 11 37 51
45 03 81 79 05 18 78 86 13 30 63 99 95
39 87 96 28 03 38 42 17 82 87 58 07 22 57
06 17 51 17 07 93 09 07 75 97 95 78 87 08 53
67 66 59 60 88 99 94 65 55 77 55 34 27 53 78 28
76 40 41 04 87 16 09 42 75 69 23 97 30 60 10 79 87
12 10 44 26 21 36 32 84 98 60 13 12 36 16 63 31 91 35
70 39 06 05 55 27 38 48 28 22 34 35 62 62 15 14 94 89 86
66 56 68 84 96 21 34 34 34 81 62 40 65 54 62 05 98 03 02 60
38 89 46 37 99 54 34 53 36 14 70 26 02 90 45 13 31 61 83 73 47
36 10 63 96 60 49 41 05 37 42 14 58 84 93 96 17 09 43 05 43 06 59
66 57 87 57 61 28 37 51 84 73 79 15 39 95 88 87 43 39 11 86 77 74 18
54 42 05 79 30 49 99 73 46 37 50 02 45 09 54 52 27 95 27 65 19 45 26 45
71 39 17 78 76 29 52 90 18 99 78 19 35 62 71 19 23 65 93 85 49 33 75 09 02
33 24 47 61 60 55 32 88 57 55 91 54 46 57 07 77 98 52 80 99 24 25 46 78 79 05
92 09 13 55 10 67 26 78 76 82 63 49 51 31 24 68 05 57 07 54 69 21 67 43 17 63 12
24 59 06 08 98 74 66 26 61 60 13 03 09 09 24 30 71 08 88 70 72 70 29 90 11 82 41 34
66 82 67 04 36 60 92 77 91 85 62 49 59 61 30 90 29 94 26 41 89 04 53 22 83 41 09 74 90
48 28 26 37 28 52 77 26 51 32 18 98 79 36 62 13 17 08 19 54 89 29 73 68 42 14 08 16 70 37
37 60 69 70 72 71 09 59 13 60 38 13 57 36 09 30 43 89 30 39 15 02 44 73 05 73 26 63 56 86 12
55 55 85 50 62 99 84 77 28 85 03 21 27 22 19 26 82 69 54 04 13 07 85 14 01 15 70 59 89 95 10 19
04 09 31 92 91 38 92 86 98 75 21 05 64 42 62 84 36 20 73 42 21 23 22 51 51 79 25 45 85 53 03 43 22
75 63 02 49 14 12 89 14 60 78 92 16 44 82 38 30 72 11 46 52 90 27 08 65 78 03 85 41 57 79 39 52 33 48
78 27 56 56 39 13 19 43 86 72 58 95 39 07 04 34 21 98 39 15 39 84 89 69 84 46 37 57 59 35 59 50 26 15 93
42 89 36 27 78 91 24 11 17 41 05 94 07 69 51 96 03 96 47 90 90 45 91 20 50 56 10 32 36 49 04 53 85 92 25 65
52 09 61 30 61 97 66 21 96 92 98 90 06 34 96 60 32 69 68 33 75 84 18 31 71 50 84 63 03 03 19 11 28 42 75 45 45
61 31 61 68 96 34 49 39 05 71 76 59 62 67 06 47 96 99 34 21 32 47 52 07 71 60 42 72 94 56 82 83 84 40 94 87 82 46
01 20 60 14 17 38 26 78 66 81 45 95 18 51 98 81 48 16 53 88 37 52 69 95 72 93 22 34 98 20 54 27 73 61 56 63 60 34 63
93 42 94 83 47 61 27 51 79 79 45 01 44 73 31 70 83 42 88 25 53 51 30 15 65 94 80 44 61 84 12 77 02 62 02 65 94 42 14 94
32 73 09 67 68 29 74 98 10 19 85 48 38 31 85 67 53 93 93 77 47 67 39 72 94 53 18 43 77 40 78 32 29 59 24 06 02 83 50 60 66
32 01 44 30 16 51 15 81 98 15 10 62 86 79 50 62 45 60 70 38 31 85 65 61 64 06 69 84 14 22 56 43 09 48 66 69 83 91 60 40 36 61
92 48 22 99 15 95 64 43 01 16 94 02 99 19 17 69 11 58 97 56 89 31 77 45 67 96 12 73 08 20 36 47 81 44 50 64 68 85 40 81 85 52 09
91 35 92 45 32 84 62 15 19 64 21 66 06 01 52 80 62 59 12 25 88 28 91 50 40 16 22 99 92 79 87 51 21 77 74 77 07 42 38 42 74 83 02 05
46 19 77 66 24 18 05 32 02 84 31 99 92 58 96 72 91 36 62 99 55 29 53 42 12 37 26 58 89 50 66 19 82 75 12 48 24 87 91 85 02 07 03 76 86
99 98 84 93 07 17 33 61 92 20 66 60 24 66 40 30 67 05 37 29 24 96 03 27 70 62 13 04 45 47 59 88 43 20 66 15 46 92 30 04 71 66 78 70 53 99
67 60 38 06 88 04 17 72 10 99 71 07 42 25 54 05 26 64 91 50 45 71 06 30 67 48 69 82 08 56 80 67 18 46 66 63 01 20 08 80 47 07 91 16 03 79 87
18 54 78 49 80 48 77 40 68 23 60 88 58 80 33 57 11 69 55 53 64 02 94 49 60 92 16 35 81 21 82 96 25 24 96 18 02 05 49 03 50 77 06 32 84 27 18 38
68 01 50 04 03 21 42 94 53 24 89 05 92 26 52 36 68 11 85 01 04 42 02 45 15 06 50 04 53 73 25 74 81 88 98 21 67 84 79 97 99 20 95 04 40 46 02 58 87
94 10 02 78 88 52 21 03 88 60 06 53 49 71 20 91 12 65 07 49 21 22 11 41 58 99 36 16 09 48 17 24 52 36 23 15 72 16 84 56 02 99 43 76 81 71 29 39 49 17
64 39 59 84 86 16 17 66 03 09 43 06 64 18 63 29 68 06 23 07 87 14 26 35 17 12 98 41 53 64 78 18 98 27 28 84 80 67 75 62 10 11 76 90 54 10 05 54 41 39 66
43 83 18 37 32 31 52 29 95 47 08 76 35 11 04 53 35 43 34 10 52 57 12 36 20 39 40 55 78 44 07 31 38 26 08 15 56 88 86 01 52 62 10 24 32 05 60 65 53 28 57 99
03 50 03 52 07 73 49 92 66 80 01 46 08 67 25 36 73 93 07 42 25 53 13 96 76 83 87 90 54 89 78 22 78 91 73 51 69 09 79 94 83 53 09 40 69 62 10 79 49 47 03 81 30
71 54 73 33 51 76 59 54 79 37 56 45 84 17 62 21 98 69 41 95 65 24 39 37 62 03 24 48 54 64 46 82 71 78 33 67 09 16 96 68 52 74 79 68 32 21 13 78 96 60 09 69 20 36
73 26 21 44 46 38 17 83 65 98 07 23 52 46 61 97 33 13 60 31 70 15 36 77 31 58 56 93 75 68 21 36 69 53 90 75 25 82 39 50 65 94 29 30 11 33 11 13 96 02 56 47 07 49 02
76 46 73 30 10 20 60 70 14 56 34 26 37 39 48 24 55 76 84 91 39 86 95 61 50 14 53 93 64 67 37 31 10 84 42 70 48 20 10 72 60 61 84 79 69 65 99 73 89 25 85 48 92 56 97 16
03 14 80 27 22 30 44 27 67 75 79 32 51 54 81 29 65 14 19 04 13 82 04 91 43 40 12 52 29 99 07 76 60 25 01 07 61 71 37 92 40 47 99 66 57 01 43 44 22 40 53 53 09 69 26 81 07
49 80 56 90 93 87 47 13 75 28 87 23 72 79 32 18 27 20 28 10 37 59 21 18 70 04 79 96 03 31 45 71 81 06 14 18 17 05 31 50 92 79 23 47 09 39 47 91 43 54 69 47 42 95 62 46 32 85
37 18 62 85 87 28 64 05 77 51 47 26 30 65 05 70 65 75 59 80 42 52 25 20 44 10 92 17 71 95 52 14 77 13 24 55 11 65 26 91 01 30 63 15 49 48 41 17 67 47 03 68 20 90 98 32 04 40 68
90 51 58 60 06 55 23 68 05 19 76 94 82 36 96 43 38 90 87 28 33 83 05 17 70 83 96 93 06 04 78 47 80 06 23 84 75 23 87 72 99 14 50 98 92 38 90 64 61 58 76 94 36 66 87 80 51 35 61 38
57 95 64 06 53 36 82 51 40 33 47 14 07 98 78 65 39 58 53 06 50 53 04 69 40 68 36 69 75 78 75 60 03 32 39 24 74 47 26 90 13 40 44 71 90 76 51 24 36 50 25 45 70 80 61 80 61 43 90 64 11
18 29 86 56 68 42 79 10 42 44 30 12 96 18 23 18 52 59 02 99 67 46 60 86 43 38 55 17 44 93 42 21 55 14 47 34 55 16 49 24 23 29 96 51 55 10 46 53 27 92 27 46 63 57 30 65 43 27 21 20 24 83
81 72 93 19 69 52 48 01 13 83 92 69 20 48 69 59 20 62 05 42 28 89 90 99 32 72 84 17 08 87 36 03 60 31 36 36 81 26 97 36 48 54 56 56 27 16 91 08 23 11 87 99 33 47 02 14 44 73 70 99 43 35 33
90 56 61 86 56 12 70 59 63 32 01 15 81 47 71 76 95 32 65 80 54 70 34 51 40 45 33 04 64 55 78 68 88 47 31 47 68 87 03 84 23 44 89 72 35 08 31 76 63 26 90 85 96 67 65 91 19 14 17 86 04 71 32 95
37 13 04 22 64 37 37 28 56 62 86 33 07 37 10 44 52 82 52 06 19 52 57 75 90 26 91 24 06 21 14 67 76 30 46 14 35 89 89 41 03 64 56 97 87 63 22 34 03 79 17 45 11 53 25 56 96 61 23 18 63 31 37 37 47
77 23 26 70 72 76 77 04 28 64 71 69 14 85 96 54 95 48 06 62 99 83 86 77 97 75 71 66 30 19 57 90 33 01 60 61 14 12 90 99 32 77 56 41 18 14 87 49 10 14 90 64 18 50 21 74 14 16 88 05 45 73 82 47 74 44
22 97 41 13 34 31 54 61 56 94 03 24 59 27 98 77 04 09 37 40 12 26 87 09 71 70 07 18 64 57 80 21 12 71 83 94 60 39 73 79 73 19 97 32 64 29 41 07 48 84 85 67 12 74 95 20 24 52 41 67 56 61 29 93 35 72 69
72 23 63 66 01 11 07 30 52 56 95 16 65 26 83 90 50 74 60 18 16 48 43 77 37 11 99 98 30 94 91 26 62 73 45 12 87 73 47 27 01 88 66 99 21 41 95 80 02 53 23 32 61 48 32 43 43 83 14 66 95 91 19 81 80 67 25 88
08 62 32 18 92 14 83 71 37 96 11 83 39 99 05 16 23 27 10 67 02 25 44 11 55 31 46 64 41 56 44 74 26 81 51 31 45 85 87 09 81 95 22 28 76 69 46 48 64 87 67 76 27 89 31 11 74 16 62 03 60 94 42 47 09 34 94 93 72
56 18 90 18 42 17 42 32 14 86 06 53 33 95 99 35 29 15 44 20 49 59 25 54 34 59 84 21 23 54 35 90 78 16 93 13 37 88 54 19 86 67 68 55 66 84 65 42 98 37 87 56 33 28 58 38 28 38 66 27 52 21 81 15 08 22 97 32 85 27
91 53 40 28 13 34 91 25 01 63 50 37 22 49 71 58 32 28 30 18 68 94 23 83 63 62 94 76 80 41 90 22 82 52 29 12 18 56 10 08 35 14 37 57 23 65 67 40 72 39 93 39 70 89 40 34 07 46 94 22 20 05 53 64 56 30 05 56 61 88 27
23 95 11 12 37 69 68 24 66 10 87 70 43 50 75 07 62 41 83 58 95 93 89 79 45 39 02 22 05 22 95 43 62 11 68 29 17 40 26 44 25 71 87 16 70 85 19 25 59 94 90 41 41 80 61 70 55 60 84 33 95 76 42 63 15 09 03 40 38 12 03 32
09 84 56 80 61 55 85 97 16 94 82 94 98 57 84 30 84 48 93 90 71 05 95 90 73 17 30 98 40 64 65 89 07 79 09 19 56 36 42 30 23 69 73 72 07 05 27 61 24 31 43 48 71 84 21 28 26 65 65 59 65 74 77 20 10 81 61 84 95 08 52 23 70
47 81 28 09 98 51 67 64 35 51 59 36 92 82 77 65 80 24 72 53 22 07 27 10 21 28 30 22 48 82 80 48 56 20 14 43 18 25 50 95 90 31 77 08 09 48 44 80 90 22 93 45 82 17 13 96 25 26 08 73 34 99 06 49 24 06 83 51 40 14 15 10 25 01
54 25 10 81 30 64 24 74 75 80 36 75 82 60 22 69 72 91 45 67 03 62 79 54 89 74 44 83 64 96 66 73 44 30 74 50 37 05 09 97 70 01 60 46 37 91 39 75 75 18 58 52 72 78 51 81 86 52 08 97 01 46 43 66 98 62 81 18 70 93 73 08 32 46 34
96 80 82 07 59 71 92 53 19 20 88 66 03 26 26 10 24 27 50 82 94 73 63 08 51 33 22 45 19 13 58 33 90 15 22 50 36 13 55 06 35 47 82 52 33 61 36 27 28 46 98 14 73 20 73 32 16 26 80 53 47 66 76 38 94 45 02 01 22 52 47 96 64 58 52 39
88 46 23 39 74 63 81 64 20 90 33 33 76 55 58 26 10 46 42 26 74 74 12 83 32 43 09 02 73 55 86 54 85 34 28 23 29 79 91 62 47 41 82 87 99 22 48 90 20 05 96 75 95 04 43 28 81 39 81 01 28 42 78 25 39 77 90 57 58 98 17 36 73 22 63 74 51
29 39 74 94 95 78 64 24 38 86 63 87 93 06 70 92 22 16 80 64 29 52 20 27 23 50 14 13 87 15 72 96 81 22 08 49 72 30 70 24 79 31 16 64 59 21 89 34 96 91 48 76 43 53 88 01 57 80 23 81 90 79 58 01 80 87 17 99 86 90 72 63 32 69 14 28 88 69
37 17 71 95 56 93 71 35 43 45 04 98 92 94 84 96 11 30 31 27 31 60 92 03 48 05 98 91 86 94 35 90 90 08 48 19 33 28 68 37 59 26 65 96 50 68 22 07 09 49 34 31 77 49 43 06 75 17 81 87 61 79 52 26 27 72 29 50 07 98 86 01 17 10 46 64 24 18 56
51 30 25 94 88 85 79 91 40 33 63 84 49 67 98 92 15 26 75 19 82 05 18 78 65 93 61 48 91 43 59 41 70 51 22 15 92 81 67 91 46 98 11 11 65 31 66 10 98 65 83 21 05 56 05 98 73 67 46 74 69 34 08 30 05 52 07 98 32 95 30 94 65 50 24 63 28 81 99 57
19 23 61 36 09 89 71 98 65 17 30 29 89 26 79 74 94 11 44 48 97 54 81 55 39 66 69 45 28 47 13 86 15 76 74 70 84 32 36 33 79 20 78 14 41 47 89 28 81 05 99 66 81 86 38 26 06 25 13 60 54 55 23 53 27 05 89 25 23 11 13 54 59 54 56 34 16 24 53 44 06
13 40 57 72 21 15 60 08 04 19 11 98 34 45 09 97 86 71 03 15 56 19 15 44 97 31 90 04 87 87 76 08 12 30 24 62 84 28 12 85 82 53 99 52 13 94 06 65 97 86 09 50 94 68 69 74 30 67 87 94 63 07 78 27 80 36 69 41 06 92 32 78 37 82 30 05 18 87 99 72 19 99
44 20 55 77 69 91 27 31 28 81 80 27 02 07 97 23 95 98 12 25 75 29 47 71 07 47 78 39 41 59 27 76 13 15 66 61 68 35 69 86 16 53 67 63 99 85 41 56 08 28 33 40 94 76 90 85 31 70 24 65 84 65 99 82 19 25 54 37 21 46 33 02 52 99 51 33 26 04 87 02 08 18 96
54 42 61 45 91 06 64 79 80 82 32 16 83 63 42 49 19 78 65 97 40 42 14 61 49 34 04 18 25 98 59 30 82 72 26 88 54 36 21 75 03 88 99 53 46 51 55 78 22 94 34 40 68 87 84 25 30 76 25 08 92 84 42 61 40 38 09 99 40 23 29 39 46 55 10 90 35 84 56 70 63 23 91 39
52 92 03 71 89 07 09 37 68 66 58 20 44 92 51 56 13 71 79 99 26 37 02 06 16 67 36 52 58 16 79 73 56 60 59 27 44 77 94 82 20 50 98 33 09 87 94 37 40 83 64 83 58 85 17 76 53 02 83 52 22 27 39 20 48 92 45 21 09 42 24 23 12 37 52 28 50 78 79 20 86 62 73 20 59
54 96 80 15 91 90 99 70 10 09 58 90 93 50 81 99 54 38 36 10 30 11 35 84 16 45 82 18 11 97 36 43 96 79 97 65 40 48 23 19 17 31 64 52 65 65 37 32 65 76 99 79 34 65 79 27 55 33 03 01 33 27 61 28 66 08 04 70 49 46 48 83 01 45 19 96 13 81 14 21 31 79 93 85 50 05
92 92 48 84 59 98 31 53 23 27 15 22 79 95 24 76 05 79 16 93 97 89 38 89 42 83 02 88 94 95 82 21 01 97 48 39 31 78 09 65 50 56 97 61 01 07 65 27 21 23 14 15 80 97 44 78 49 35 33 45 81 74 34 05 31 57 09 38 94 07 69 54 69 32 65 68 46 68 78 90 24 28 49 51 45 86 35
41 63 89 76 87 31 86 09 46 14 87 82 22 29 47 16 13 10 70 72 82 95 48 64 58 43 13 75 42 69 21 12 67 13 64 85 58 23 98 09 37 76 05 22 31 12 66 50 29 99 86 72 45 25 10 28 19 06 90 43 29 31 67 79 46 25 74 14 97 35 76 37 65 46 23 82 06 22 30 76 93 66 94 17 96 13 20 72
63 40 78 08 52 09 90 41 70 28 36 14 46 44 85 96 24 52 58 15 87 37 05 98 99 39 13 61 76 38 44 99 83 74 90 22 53 80 56 98 30 51 63 39 44 30 91 91 04 22 27 73 17 35 53 18 35 45 54 56 27 78 48 13 69 36 44 38 71 25 30 56 15 22 73 43 32 69 59 25 93 83 45 11 34 94 44 39 92
12 36 56 88 13 96 16 12 55 54 11 47 19 78 17 17 68 81 77 51 42 55 99 85 66 27 81 79 93 42 65 61 69 74 14 01 18 56 12 01 58 37 91 22 42 66 83 25 19 04 96 41 25 45 18 69 96 88 36 93 10 12 98 32 44 83 83 04 72 91 04 27 73 07 34 37 71 60 59 31 01 54 54 44 96 93 83 36 04 45
30 18 22 20 42 96 65 79 17 41 55 69 94 81 29 80 91 31 85 25 47 26 43 49 02 99 34 67 99 76 16 14 15 93 08 32 99 44 61 77 67 50 43 55 87 55 53 72 17 46 62 25 50 99 73 05 93 48 17 31 70 80 59 09 44 59 45 13 74 66 58 94 87 73 16 14 85 38 74 99 64 23 79 28 71 42 20 37 82 31 23
51 96 39 65 46 71 56 13 29 68 53 86 45 33 51 49 12 91 21 21 76 85 02 17 98 15 46 12 60 21 88 30 92 83 44 59 42 50 27 88 46 86 94 73 45 54 23 24 14 10 94 21 20 34 23 51 04 83 99 75 90 63 60 16 22 33 83 70 11 32 10 50 29 30 83 46 11 05 31 17 86 42 49 01 44 63 28 60 07 78 95 40
44 61 89 59 04 49 51 27 69 71 46 76 44 04 09 34 56 39 15 06 94 91 75 90 65 27 56 23 74 06 23 33 36 69 14 39 05 34 35 57 33 22 76 46 56 10 61 65 98 09 16 69 04 62 65 18 99 76 49 18 72 66 73 83 82 40 76 31 89 91 27 88 17 35 41 35 32 51 32 67 52 68 74 85 80 57 07 11 62 66 47 22 67
65 37 19 97 26 17 16 24 24 17 50 37 64 82 24 36 32 11 68 34 69 31 32 89 79 93 96 68 49 90 14 23 04 04 67 99 81 74 70 74 36 96 68 09 64 39 88 35 54 89 96 58 66 27 88 97 32 14 06 35 78 20 71 06 85 66 57 02 58 91 72 05 29 56 73 48 86 52 09 93 22 57 79 42 12 01 31 68 17 59 63 76 07 77
73 81 14 13 17 20 11 09 01 83 08 85 91 70 84 63 62 77 37 07 47 01 59 95 39 69 39 21 99 09 87 02 97 16 92 36 74 71 90 66 33 73 73 75 52 91 11 12 26 53 05 26 26 48 61 50 90 65 01 87 42 47 74 35 22 73 24 26 56 70 52 05 48 41 31 18 83 27 21 39 80 85 26 08 44 02 71 07 63 22 05 52 19 08 20
17 25 21 11 72 93 33 49 64 23 53 82 03 13 91 65 85 02 40 05 42 31 77 42 05 36 06 54 04 58 07 76 87 83 25 57 66 12 74 33 85 37 74 32 20 69 03 97 91 68 82 44 19 14 89 28 85 85 80 53 34 87 58 98 88 78 48 65 98 40 11 57 10 67 70 81 60 79 74 72 97 59 79 47 30 20 54 80 89 91 14 05 33 36 79 39
60 85 59 39 60 07 57 76 77 92 06 35 15 72 23 41 45 52 95 18 64 79 86 53 56 31 69 11 91 31 84 50 44 82 22 81 41 40 30 42 30 91 48 94 74 76 64 58 74 25 96 57 14 19 03 99 28 83 15 75 99 01 89 85 79 50 03 95 32 67 44 08 07 41 62 64 29 20 14 76 26 55 48 71 69 66 19 72 44 25 14 01 48 74 12 98 07
64 66 84 24 18 16 27 48 20 14 47 69 30 86 48 40 23 16 61 21 51 50 26 47 35 33 91 28 78 64 43 68 04 79 51 08 19 60 52 95 06 68 46 86 35 97 27 58 04 65 30 58 99 12 12 75 91 39 50 31 42 64 70 04 46 07 98 73 98 93 37 89 77 91 64 71 64 65 66 21 78 62 81 74 42 20 83 70 73 95 78 45 92 27 34 53 71 15
30 11 85 31 34 71 13 48 05 14 44 03 19 67 23 73 19 57 06 90 94 72 57 69 81 62 59 68 88 57 55 69 49 13 07 87 97 80 89 05 71 05 05 26 38 40 16 62 45 99 18 38 98 24 21 26 62 74 69 04 85 57 77 35 58 67 91 79 79 57 86 28 66 34 72 51 76 78 36 95 63 90 08 78 47 63 45 31 22 70 52 48 79 94 15 77 61 67 68
23 33 44 81 80 92 93 75 94 88 23 61 39 76 22 03 28 94 32 06 49 65 41 34 18 23 08 47 62 60 03 63 33 13 80 52 31 54 73 43 70 26 16 69 57 87 83 31 03 93 70 81 47 95 77 44 29 68 39 51 56 59 63 07 25 70 07 77 43 53 64 03 94 42 95 39 18 01 66 21 16 97 20 50 90 16 70 10 95 69 29 06 25 61 41 26 15 59 63 35";
			#endregion

			var data_array = data.Split(new string[] { "\r\n" }, StringSplitOptions.None).Select(d => d.Split(' ').Select(dn => int.Parse(dn)).ToArray()).ToArray();
			for (int i = data_array.Length - 2; i >= 0; i--)
			{
				for (int j = 0; j < data_array[i].Length; j++)
				{
					data_array[i][j] += Math.Max(data_array[i + 1][j], data_array[i + 1][j + 1]);
				}
			}

			return data_array[0][0];
		}

		[SolutionInfo(Links = "http://www.mathblog.dk/project-euler-65-numerator-continued-fraction-e/")]
		private static dynamic Problem65()
		{
			Func<long> solve = () =>
			{
				const int upperbound = 100;

				BigInteger d = 1;
				BigInteger n = 2;

				for (int i = 2; i <= upperbound; i++)
				{
					BigInteger temp = d;
					int c = (i % 3 == 0) ? 2 * (i / 3) : 1;
					d = n;
					n = c * d + temp;
				}
				long sum = n.ToString().Select(c => int.Parse(c + "")).Sum();
				return sum;
			};
			return solve();
		}

		private static dynamic Problem63()
		{
			int result = 0;
			int lower = 0;
			int n = 1;
			while (lower < 10)
			{
				lower = (int)Math.Ceiling(Math.Pow(10, (n - 1.0) / n));
				result += 10 - lower;
				n++;
			}
			return result;
		}

		private static dynamic Problem62()
		{
			var groups = new Dictionary<string, long[]>();
			for (long i = 2; i < 10000; i++)
			{
				long prod = i * i * i;
				var digits = prod.ToString().Select(c => int.Parse("" + c)).ToList();
				digits.Sort();
				var s = string.Join("", digits);
				if (!groups.ContainsKey(s))
				{
					groups.Add(s, new long[2]);
					groups[s][1] = 0;
				}
				groups[s][0]++;
				if (groups[s][1] == 0 || groups[s][1] > prod)
				{
					groups[s][1] = prod;
				}
			}
			long smallest = 0;
			foreach (var k in groups.Keys)
			{
				if (groups[k][0] == 5)
				{
					if (smallest == 0 || smallest > groups[k][1])
					{
						smallest = groups[k][1];
					}
				}
			}
			return smallest;
		}

		private static dynamic Problem61()
		{
			int[] solution = new int[6];
			int[][] numbers = new int[6][];

			Func<int, int[]> generateNumbers = (int type) =>
			{
				List<int> new_numbers = new List<int>();
				int n = 0;
				int number = 0;
				while (number < 10000)
				{
					n++;
					switch (type)
					{
						case 0:
							//Triangle numbers
							number = n * (n + 1) / 2;
							break;
						case 1:
							// Square numbers
							number = n * n;
							break;
						case 2:
							// Pentagonal numbers
							number = n * (3 * n - 1) / 2;
							break;
						case 3:
							//Hexagonal numbers
							number = n * (2 * n - 1);
							break;
						case 4:
							//Heptagonal numbers
							number = n * (5 * n - 3) / 2;
							break;
						case 5:
							//Octagonal numbers
							number = n * (3 * n - 2);
							break;
					}
					if (number > 999)
						new_numbers.Add(number);
				}
				return new_numbers.ToArray();
			};

			Func<int, int, bool> FindNext = null;
			FindNext = (int last, int length) =>
			{
				for (int i = 0; i < solution.Length; i++)
				{
					if (solution[i] != 0) continue;
					for (int j = 0; j < numbers[i].Length; j++)
					{
						bool unique = true;
						for (int k = 0; k < solution.Length; k++)
						{
							if (numbers[i][j] == solution[k])
							{
								unique = false;
								break;
							}
						}

						if (unique && ((numbers[i][j] / 100) == (solution[last] % 100)))
						{
							solution[i] = numbers[i][j];
							if (length == 5)
							{
								if (solution[5] / 100 == solution[i] % 100) return true;
							}
							if (FindNext(i, length + 1)) return true;
						}
					}
					solution[i] = 0;
				}
				return false;
			};

			int result = int.MaxValue;
			for (int i = 0; i < 6; i++)
			{
				numbers[i] = generateNumbers(i);
			}

			for (int i = 0; i < numbers[5].Length; i++)
			{
				solution[5] = numbers[5][i];
				if (FindNext(5, 1)) break;
			}
			result = solution.Sum();
			return result;
		}

		private static dynamic Problem60()
		{
			const int limit = 10000;

			Func<long, bool> TrialDivisionPrimeTest = (long n) =>
			{
				if (n <= 1) return false;
				if (n == 2) return true;
				if (n % 2 == 0) return false;
				if (n < 9) return true;
				if (n % 3 == 0) return false;

				long counter = 5;
				while ((counter * counter) <= n)
				{
					if (n % counter == 0) return false;
					if (n % (counter + 2) == 0) return false;
					counter += 6;
				}

				return true;
			};

			var primes_list = Misc.esieve(limit).ToList();

			long foundSum = 0;
			Action<int, List<int>> search = null;
			search = (int n, List<int> found) =>
			{
				bool correct = true;
				if (found.Count > 1)
				{
					for (int k1 = 0; k1 < found.Count - 1; k1++)
					{
						for (int k2 = k1 + 1; k2 < found.Count; k2++)
						{
							if (!TrialDivisionPrimeTest(long.Parse(primes_list[found[k1]].ToString() + primes_list[found[k2]].ToString())))
							{
								correct = false;
								break;
							}
							if (!TrialDivisionPrimeTest(long.Parse(primes_list[found[k2]].ToString() + primes_list[found[k1]].ToString())))
							{
								correct = false;
								break;
							}
						}
						if (!correct)
						{
							break;
						}
					}
				}
				if (!correct)
				{
					return;
				}
				if (found.Count == 5)
				{
					long foundSumLocal = 0;
					foreach (var k1 in found)
					{
						foundSumLocal += primes_list[k1];
					}
					if (foundSum == 0 || foundSumLocal < foundSum)
					{
						foundSum = foundSumLocal;
					}
				}
				else
				{
					for (int k1 = n + 1; k1 < primes_list.Count; k1++)
					{
						found.Add(k1);
						search(k1, found);
						found.Remove(k1);
					}
				}
			};

			Func<int, int, bool> check = (int n1, int n2) =>
			{
				return TrialDivisionPrimeTest(long.Parse(primes_list[n1].ToString() + primes_list[n2].ToString())) &&
					TrialDivisionPrimeTest(long.Parse(primes_list[n2].ToString() + primes_list[n1].ToString()));

			};

			for (int i = 0; i < primes_list.Count; i++)
			{
				for (int i2 = i + 1; i2 < primes_list.Count; i2++)
				{
					if (!check(i, i2))
					{
						continue;
					}
					for (int i3 = i2 + 1; i3 < primes_list.Count; i3++)
					{
						if (!check(i, i3) || !check(i2, i3))
						{
							continue;
						}
						for (int i4 = i3 + 1; i4 < primes_list.Count; i4++)
						{
							if (!check(i, i4) || !check(i2, i4) || !check(i3, i4))
							{
								continue;
							}
							for (int i5 = i4 + 1; i5 < primes_list.Count; i5++)
							{
								if (!check(i, i5) || !check(i2, i5) || !check(i3, i5) || !check(i4, i5))
								{
									continue;
								}
								long currentSum = primes_list[i] + primes_list[i2] + primes_list[i3] +
									primes_list[i4] + primes_list[i5];
								if (foundSum == 0 || currentSum < foundSum)
								{
									foundSum = currentSum;
								}
							}
						}
					}
				}
			}
			return foundSum;
		}

		[SolutionInfo(Links = "http://www.mathblog.dk/project-euler-59-xor-encryption/")]
		private static dynamic Problem59()
		{
			var possibleChars = new HashSet<char>() { ' ', ',', ':', ';', '.', '(', ')', '{', '}', '\'', '!', '?' };

			Func<List<byte>, int[], Tuple<bool, long>> check = (List<byte> data, int[] key) =>
			{
				long sum = 0;
				for (int i = 0; i < data.Count; i++)
				{
					var cB = data[i] ^ key[i % 3];
					sum += cB;
					var ch = (char)cB;
					if (!(char.IsLetter(ch) || char.IsDigit(ch) || possibleChars.Contains(ch)))
						return new Tuple<bool, long>(false, 0);
				}
				return new Tuple<bool, long>(true, sum);
			};

			Func<long> solve = () =>
			{
				var data = File.ReadAllText("cipher1.txt").Split(',').Select(c => byte.Parse(c)).ToList();
				long sum = 0;
				for (var c1 = 0; c1 <= 255; c1++)
				{
					for (var c2 = 0; c2 <= 255; c2++)
					{
						for (var c3 = 0; c3 <= 255; c3++)
						{
							var fitAns = check(data, new int[] { c1, c2, c3 });
							if (fitAns.Item1)
							{
								sum = fitAns.Item2;
								break;
							}
						}
						if (sum > 0)
							break;
					}
					if (sum > 0)
						break;
				}
				return sum;
			};
			return solve();
		}

		private static dynamic Problem58()
		{
			Func<int, bool> TrialDivisionPrimeTest = (int n) =>
			{
				if (n <= 1) return false;
				if (n == 2) return true;
				if (n % 2 == 0) return false;
				if (n < 9) return true;
				if (n % 3 == 0) return false;

				long counter = 5;
				while ((counter * counter) <= n)
				{
					if (n % counter == 0) return false;
					if (n % (counter + 2) == 0) return false;
					counter += 6;
				}

				return true;
			};

			int num = 49;
			int side = 7;
			int primeCnt = 8;
			while (((double)primeCnt) / (side * 2 - 1) > 0.10)
			{
				side += 2;
				for (int i = 1; i <= 4; i++)
				{
					num += (side - 1);
					if (TrialDivisionPrimeTest(num))
					{
						primeCnt++;
					}
				}
			}
			return side;
		}

		private static dynamic Problem57()
		{
			const int limit = 1000;
			int result = 0;

			BigInteger den = 2;
			BigInteger num = 3;

			for (int i = 1; i < limit; i++)
			{
				num += 2 * den;
				den = num - den;
				if ((int)BigInteger.Log10(num) > (int)BigInteger.Log10(den))
					result++;
			}
			return result;
		}

		private static dynamic Problem56()
		{
			var maxsum = 0;
			for (int a = 2; a < 100; a++)
			{
				for (int b = 2; b < 100; b++)
				{
					BigInteger num = BigInteger.Pow(a, b);
					var sum = 0;
					foreach (var c in num.ToString())
					{
						sum += int.Parse(c + "");
					}
					if (sum > maxsum)
					{
						maxsum = sum;
					}
				}
			}
			return maxsum;
		}

		private static dynamic Problem55()
		{
			var count = 0;
			for (int i = 10; i < 10000; i++)
			{
				BigInteger i2 = i;
				BigInteger i3 = BigInteger.Parse(string.Join("", i.ToString().Reverse()));
				for (int j = 1; j <= 50; j++)
				{
					BigInteger sum = i2 + i3;
					BigInteger sum_reverse = BigInteger.Parse(string.Join("", sum.ToString().Reverse()));
					if (sum == sum_reverse)
					{
						count++;
						break;
					}
					i2 = sum;
					i3 = sum_reverse;
				}
			}
			return 10000 - 1 - 9 - count;
		}

		enum Suit { Heart, Spade, Club, Diamond };
		private class Card : IComparable
		{
			public Suit Suit { get; set; }
			public int Value { get; set; }

			public int CompareTo(object o)
			{
				if (o is Card)
				{
					Card c = (Card)o;
					if (Value < c.Value)
						return -1;
					else if (Value > c.Value)
						return 1;
					return 0;
				}
				throw new ArgumentException("Object is not a Card");
			}
		}
		[SolutionInfo(Links = "http://www.mathblog.dk/project-euler-54-poker-hands/")]
		private static dynamic Problem54()
		{
			Func<Card[], int> IsStraight = (Card[] h) =>
			{
				for (int i = 0; i < 4; i++)
				{
					if (h[i].Value != h[i + 1].Value - 1)
					{
						return -1;
					}
				}
				return h[4].Value;
			};

			Func<Card[], int> IsFlush = (Card[] h) =>
			{
				for (int i = 0; i < 4; i++)
				{
					if (h[i].Suit != h[i + 1].Suit)
					{
						return -1;
					}
				}
				return h[4].Value;
			};

			Func<Card[], int> IsStraightFlush = (Card[] h) =>
			{
				if (IsFlush(h) > 0 && IsStraight(h) > 0)
				{
					return h[4].Value;
				}
				return -1;
			};

			Func<Card[], int> IsRoyalFlush = (Card[] h) =>
			{
				if (IsFlush(h) == 14) return 14;
				return -1;
			};

			Func<Card[], int> IsFourOfAKind = (Card[] h) =>
			{
				if (h[0].Value == h[1].Value &&
					h[1].Value == h[2].Value &&
					h[2].Value == h[3].Value)
					return h[0].Value;
				if (h[1].Value == h[2].Value &&
					h[2].Value == h[3].Value &&
					h[3].Value == h[4].Value)
					return h[1].Value;
				return -1;
			};

			Func<Card[], int, int> IsFullHouse = (Card[] h, int set) =>
			{
				if (set == 1 &&
				   h[0].Value == h[1].Value &&
				   h[1].Value == h[2].Value &&
				   h[3].Value == h[4].Value)
					return h[0].Value;
				if (set == 2 &&
					h[0].Value == h[1].Value &&
				   h[1].Value == h[2].Value &&
				   h[3].Value == h[4].Value)
					return h[4].Value;
				if (set == 1 &&
				   h[0].Value == h[1].Value &&
				   h[2].Value == h[3].Value &&
				   h[3].Value == h[4].Value)
					return h[4].Value;
				if (set == 2 &&
					h[0].Value == h[1].Value &&
				   h[2].Value == h[3].Value &&
				   h[3].Value == h[4].Value)
					return h[0].Value;
				return -1;
			};

			Func<Card[], int> IsThreeOfAKind = (Card[] h) =>
			{
				if (h[0].Value == h[1].Value &&
				   h[1].Value == h[2].Value)
					return h[0].Value;

				if (h[1].Value == h[2].Value &&
				   h[2].Value == h[3].Value)
					return h[1].Value;

				if (h[2].Value == h[3].Value &&
				   h[3].Value == h[4].Value)
					return h[2].Value;

				return -1;
			};

			Func<Card[], int, int> IsTwoPairs = (Card[] h, int set) =>
			{
				if (set == 1 &&
					h[0].Value == h[1].Value &&
					h[2].Value == h[3].Value)
					return h[0].Value;
				if (set == 2 &&
					h[0].Value == h[1].Value &&
					h[2].Value == h[3].Value)
					return h[2].Value;
				if (set == 1 &&
					h[0].Value == h[1].Value &&
					h[3].Value == h[4].Value)
					return h[0].Value;
				if (set == 2 &&
					h[0].Value == h[1].Value &&
					h[3].Value == h[4].Value)
					return h[3].Value;

				if (set == 1 &&
					h[1].Value == h[2].Value &&
					h[3].Value == h[4].Value)
					return h[1].Value;
				if (set == 2 &&
					h[1].Value == h[2].Value &&
					h[3].Value == h[4].Value)
					return h[3].Value;
				return -1;
			};

			Func<Card[], int> IsOnePair = (Card[] h) =>
			{
				if (h[0].Value == h[1].Value) return h[0].Value;
				if (h[1].Value == h[2].Value) return h[1].Value;
				if (h[2].Value == h[3].Value) return h[2].Value;
				if (h[3].Value == h[4].Value) return h[3].Value;

				return -1;
			};

			Func<Card[], int, int> IsHighCard = (Card[] h, int card) =>
			{
				return h[4 - card].Value;
			};

			Func<Card[], Card[], bool> DidPlayer1Win = (Card[] hand1, Card[] hand2) =>
			{
				if (IsRoyalFlush(hand1) != IsRoyalFlush(hand2)) return IsRoyalFlush(hand1) > IsRoyalFlush(hand2);
				if (IsStraightFlush(hand1) != IsStraightFlush(hand2)) return IsStraightFlush(hand1) > IsStraightFlush(hand2);
				if (IsFourOfAKind(hand1) != IsFourOfAKind(hand2)) return IsFourOfAKind(hand1) > IsFourOfAKind(hand2);
				if (IsFullHouse(hand1, 1) != IsFullHouse(hand2, 1)) return IsFullHouse(hand1, 1) > IsFullHouse(hand2, 1);
				if (IsFullHouse(hand1, 2) != IsFullHouse(hand2, 2)) return IsFullHouse(hand1, 2) < IsFullHouse(hand2, 2);
				if (IsFlush(hand1) != IsFlush(hand2)) return IsFlush(hand1) > IsFlush(hand2);
				if (IsStraight(hand1) != IsStraight(hand2)) return IsStraight(hand1) > IsStraight(hand2);
				if (IsThreeOfAKind(hand1) != IsThreeOfAKind(hand2)) return IsThreeOfAKind(hand1) > IsThreeOfAKind(hand2);
				if (IsTwoPairs(hand1, 1) != IsTwoPairs(hand2, 1)) return IsTwoPairs(hand1, 1) > IsTwoPairs(hand2, 1);
				if (IsTwoPairs(hand1, 2) != IsTwoPairs(hand2, 2)) return IsTwoPairs(hand1, 2) > IsTwoPairs(hand2, 2);
				if (IsOnePair(hand1) != IsOnePair(hand2)) return IsOnePair(hand1) > IsOnePair(hand2);
				if (IsHighCard(hand1, 0) != IsHighCard(hand2, 0)) return IsHighCard(hand1, 0) > IsHighCard(hand2, 0);
				if (IsHighCard(hand1, 1) != IsHighCard(hand2, 1)) return IsHighCard(hand1, 1) > IsHighCard(hand2, 1);
				if (IsHighCard(hand1, 2) != IsHighCard(hand2, 2)) return IsHighCard(hand1, 2) > IsHighCard(hand2, 2);
				if (IsHighCard(hand1, 3) != IsHighCard(hand2, 3)) return IsHighCard(hand1, 3) > IsHighCard(hand2, 3);

				return false;
			};

			Func<string, Suit> getSuit = (string suit) =>
			{
				if (suit == "D") return Suit.Diamond;
				if (suit == "C") return Suit.Club;
				if (suit == "H") return Suit.Heart;
				return Suit.Spade;
			};

			Func<string, int> getCardValue = (string value) =>
			{
				int intvalue;
				if (Int32.TryParse(value, out intvalue)) return intvalue;

				if (value == "T") return 10;
				if (value == "J") return 11;
				if (value == "Q") return 12;
				if (value == "K") return 13;
				if (value == "A") return 14;

				return 0;
			};

			const string FILENAME = "poker.txt";
			StreamReader reader = null;

			Func<Card[], Card[], bool> readHands = (Card[] hand1, Card[] hand2) =>
			{
				if (reader == null) reader = new StreamReader(FILENAME);

				string line;
				string[] linePieces;
				line = reader.ReadLine();
				if (line == null) return false;
				linePieces = line.Split(' ');

				for (int i = 0; i < 5; i++)
				{
					hand1[i] = new Card();
					hand1[i].Value = getCardValue(linePieces[i].Substring(0, 1));
					hand1[i].Suit = getSuit(linePieces[i].Substring(1, 1));
				}

				for (int i = 0; i < 5; i++)
				{
					hand2[i] = new Card();
					hand2[i].Value = getCardValue(linePieces[i + 5].Substring(0, 1));
					hand2[i].Suit = getSuit(linePieces[i + 5].Substring(1, 1));
				}

				return true;
			};

			Func<long> solve = () =>
			{
				Card[] hand1 = new Card[5];
				Card[] hand2 = new Card[5];
				long result = 0;
				while (readHands(hand1, hand2))
				{
					Array.Sort(hand1);
					Array.Sort(hand2);
					if (DidPlayer1Win(hand1, hand2)) result++;
				}
				return result;
			};
			return solve();
		}

		private static dynamic Problem53()
		{
			Func<int, int, int> isRight = (int n1, int r1) =>
			{
				var nom = new List<int>();
				for (int i = r1 + 1; i <= n1; i++)
				{
					nom.Add(i);
				}
				var den = new List<int>();
				for (int i = 1; i <= (n1 - r1); i++)
				{
					den.Add(i);
				}
				double nomProd = 1;
				for (int i = 0; i < nom.Count; i++)
				{
					nomProd *= nom[i];
				}
				double denProd = 1;
				for (int i = 0; i < den.Count; i++)
				{
					denProd *= den[i];
				}
				return (nomProd / denProd > 1000000 ? 1 : 0);
			};

			int count = 0;
			for (int n = 1; n <= 100; n++)
			{
				for (int r = 1; r <= n; r++)
				{
					count += isRight(n, r);
				}
			}
			return count;
		}

		private static dynamic Problem52()
		{
			Func<long, long, bool> isSameDigits = (long a, long b) =>
			{
				if (a.ToString().Length != b.ToString().Length)
				{
					return false;
				}
				var adig = new List<long>();
				while (a > 0)
				{
					adig.Add(a % 10);
					a /= 10;
				}
				adig.Sort();
				var bdig = new List<long>();
				while (b > 0)
				{
					bdig.Add(b % 10);
					b /= 10;
				}
				bdig.Sort();
				for (int i = 0; i < adig.Count; i++)
				{
					if (adig[i] != bdig[i])
					{
						return false;
					}
				}
				return true;
			};

			long k = 1;
			while (true)
			{
				if (isSameDigits(k, 2 * k) && isSameDigits(k, 3 * k) && isSameDigits(k, 4 * k)
					&& isSameDigits(k, 5 * k) && isSameDigits(k, 6 * k))
				{
					break;
				}
				k++;
			}
			return k;
		}

		private static dynamic Problem51()
		{
			const int limit = 1000000;
			
			var primes = Misc.esieve(limit);
			
			var groups = new Dictionary<string, SortedSet<long>>();

			Action<long, int, List<int>, StringBuilder, int> addToGroups = null;
			addToGroups = (long num, int d, List<int> dig, StringBuilder dig_c, int start) =>
			{
				for (int i3 = start; i3 < dig.Count; i3++)
				{
					if (d == dig[i3])
					{
						addToGroups(num, d, dig, dig_c, i3 + 1);

						var temp = dig_c[i3];
						dig_c[i3] = 'x';
						if (!groups.ContainsKey(dig_c.ToString()))
						{
							groups.Add(dig_c.ToString(), new SortedSet<long>());
						}
						groups[dig_c.ToString()].Add(num);

						addToGroups(num, d, dig, dig_c, i3 + 1);
						dig_c[i3] = temp;
					}
				}
			};

			foreach (var i in primes)
			{
				var digits = i.ToString().Select(c => int.Parse("" + c)).ToList();
				for (int i2 = 0; i2 < digits.Count; i2++)
				{
					var digits_c = new StringBuilder(i.ToString());
					digits_c[i2] = 'x';
					if (!groups.ContainsKey(digits_c.ToString()))
					{
						groups.Add(digits_c.ToString(), new SortedSet<long>());
					}
					groups[digits_c.ToString()].Add(i);
					addToGroups(i, digits[i2], digits, digits_c, i2 + 1);
				}
			}

			var res = groups.Where(kv => kv.Value.Contains(121313)).ToArray();
			var res2 = groups.Where(kv => kv.Value.Contains(20303)).ToArray();

			long smallest = 0;
			foreach (var gr in groups.Keys)
			{
				if (groups[gr].Count >= 8)
				{
					if (smallest == 0 || groups[gr].First() < smallest)
					{
						smallest = groups[gr].First();
					}
				}
			}

			return smallest;
		}

		private static dynamic Problem50()
		{
			const int limit = 1000000;
			long len = 0;
			long num = 0;
			var primes = Misc.esieve(limit);
			var primesArray = primes.ToArray();
			for (int i = 1; i < primesArray.Length; i++)
			{
				long localsum = primesArray[i];
				long locallen = 1;
				if (primes.Contains(localsum) && locallen > len)
				{
					len = locallen;
					num = localsum;
				}
				for (int i2 = i - 1; i2 > -1; i2--)
				{
					locallen++;
					localsum += primesArray[i2];
					if (localsum > limit)
					{
						break;
					}
					if (primes.Contains(localsum) && locallen > len)
					{
						len = locallen;
						num = localsum;
					}
				}
			}
			return num;
		}

		private static dynamic Problem49()
		{
			const int limit = 10000;
			var primes = Misc.esieve(limit);

			var foundPermNums = new List<int>();

			Action<List<int>, List<int>> fillPerm = null;
			fillPerm = (List<int> digits, List<int> foundNum) =>
			{
				if (foundNum.Count >= 4)
				{
					var newnum = 0;
					for (int k1 = 0; k1 < foundNum.Count; k1++)
					{
						newnum = newnum * 10 + digits[foundNum[k1]];
					}
					if (!foundPermNums.Contains(newnum))
					{
						foundPermNums.Add(newnum);
					}
				}
				else
				{
					for (int k1 = 0; k1 < digits.Count; k1++)
					{
						if (!foundNum.Contains(k1))
						{
							foundNum.Add(k1);
							fillPerm(digits, foundNum);
							foundNum.Remove(k1);
						}
					}
				}
			};
			string isFoundGlobal = "";
			for (int i = 1111; i < limit; i++)
			{
				if (primes.Contains(i))
				{
					foundPermNums.Clear();
					var digits = new List<int>();
					var i2 = i;
					while (i2 > 0)
					{
						if (i2 % 10 == 0)
						{
							break;
						}
						digits.Add(i2 % 10);
						i2 /= 10;
					}
					if (digits.Count < 4)
					{
						continue;
					}
					fillPerm(digits, new List<int>());
					foundPermNums.Sort();
					bool isFound = false;
					for (int i3 = 0; i3 < foundPermNums.Count - 1; i3++)
					{
						if (!primes.Contains(foundPermNums[i3]))
						{
							continue;
						}
						for (int i4 = i3 + 1; i4 < foundPermNums.Count; i4++)
						{
							if (!primes.Contains(foundPermNums[i4]))
							{
								continue;
							}
							var dif = foundPermNums[i4] - foundPermNums[i3];
							var next1 = foundPermNums[i3] + dif * 2;
							if (foundPermNums.Contains(next1) && primes.Contains(next1)
								&& foundPermNums[i3] != 1487)
							{
								isFound = true;
								isFoundGlobal = foundPermNums[i3].ToString()
									+ foundPermNums[i4].ToString() + next1.ToString();
								break;
							}
						}
						if (isFound)
						{
							break;
						}
					}
					if (isFound)
					{
						break;
					}
				}
			}
			return isFoundGlobal;
		}

		private static dynamic Problem48()
		{
			Func<List<int>, List<int>, int, List<int>> sum = null;
			sum = (List<int> num1, List<int> num2, int num2shift) =>
			{
				List<int> res = new List<int>();
				for (int i = 0; i < num2shift; i++)
				{
					num2.Insert(0, 0);
				}
				var newnum = 0;
				var remain = 0;
				for (int i = 0; i < Math.Max(num1.Count, num2.Count); i++)
				{
					newnum = ((i < num1.Count ? num1[i] : 0) + (i < num2.Count ? num2[i] : 0) + remain) % 10;
					res.Add(newnum);
					remain = ((i < num1.Count ? num1[i] : 0) + (i < num2.Count ? num2[i] : 0) + remain) / 10;
				}
				if (remain > 0)
				{
					res.Add(remain);
				}
				return res;
			};

			Func<List<int>, int, List<int>> prod = null;
			prod = (List<int> num1, int num2) =>
			{
				List<int> res = new List<int>();
				var newnum = 0;
				var remain = 0;
				for (int i = 0; i < num1.Count; i++)
				{
					newnum = (num1[i] * num2 + remain) % 10;
					res.Add(newnum);
					remain = (num1[i] * num2 + remain) / 10;
				}
				if (remain > 0)
				{
					res.Add(remain);
				}
				return res;
			};

			List<int> sumAll = new List<int>() { 1 };
			for (int i = 2; i < 1001; i++)
			{
				List<int> numBytes = new List<int>();
				var ia = i;
				while (ia > 0)
				{
					numBytes.Add(ia % 10);
					ia = ia / 10;
				}
				for (int j = 2; j < i + 1; j++)
				{
					var i2 = i;
					var i2pos = 0;
					List<int> sum_local = new List<int>();
					while (i2 > 0)
					{
						var nm = i2 % 10;
						var res = prod(numBytes, nm);
						sum_local = sum(sum_local, res, i2pos);
						i2 = i2 / 10;
						i2pos++;
					}
					numBytes = sum_local;
				}
				sumAll = sum(sumAll, numBytes, 0);
			}
			if (sumAll.Count < 10)
			{
				return 0;
			}
			var digits = "";
			for (int i = 9; i > -1; i--)
			{
				digits += sumAll[i].ToString();
			}
			return int.Parse(digits);
		}

		private static dynamic Problem47()
		{
			const int limit = 1000000;
			var primes = Misc.esieve(limit);

			Func<long, bool> checkNum = (long num) =>
			{
				if (primes.Contains(num))
				{
					return false;
				}
				var factorsNumber = 0;
				var divUsed = new Dictionary<long, bool>();
				while (num > 1)
				{
					if (primes.Contains(num))
					{
						factorsNumber++;
						break;
					}
					foreach (var prime in primes)
					{
						if (num % prime == 0)
						{
							if (!divUsed.ContainsKey(prime))
							{
								factorsNumber++;
								divUsed.Add(prime, true);
							}
							num /= prime;
							break;
						}
					}
				}
				return (factorsNumber == 4);
			};
			long foundNum = 0;
			for (long i = 210; i < limit; i++)
			{
				if (checkNum(i) && checkNum(i - 1) && checkNum(i - 2) && checkNum(i - 3))
				{
					foundNum = i - 3;
					break;
				}
			}
			return foundNum;
		}

		private static dynamic Problem46()
		{
			const int limit = 1000000;
			var primes = Misc.esieve(limit);

			int k = 35;
			bool found = false;
			while (true)
			{
				found = false;
				int i = 2;
				while (i < k)
				{
					for (int i2 = 1; i2 < i; i2++)
					{
						if (k == i + 2 * i2 * i2)
						{
							found = true;
							break;
						}
					}
					if (found)
					{
						break;
					}
					i++;
					while (!primes.Contains(i))
					{
						i++;
					}
				}
				if (!found)
				{
					break;
				}
				k += 2;
				while (primes.Contains(k))
				{
					k += 2;
				}
			}
			return k;
		}

		private static dynamic Problem45()
		{
			double n = 285;
			n++;
			double next = 0;
			while (true)
			{
				double tn = n * (n + 1) / 2;
				//3*n^2-n-tn*2=0 
				double n2 = (1 + Math.Sqrt(1 - 4 * 3 * (-tn * 2))) / (2 * 3);
				//2*n^2-n-tn=0
				double n3 = (1 + Math.Sqrt(1 - 4 * 2 * (-tn))) / (2 * 2);
				if (n2 == Math.Floor(n2) && n3 == Math.Floor(n3))
				{
					next = tn;
					break;
				}
				n++;
			}
			return next;
		}

		private static dynamic Problem44()
		{
			Func<int, bool> checkP = (int pnum) =>
			{
				//3*n^2-1*n-2*pnum=0
				double x = (1 + Math.Sqrt(1 + 4 * 3 * 2 * pnum)) / 6;
				return (x == Math.Floor(x));
			};

			int n = 2;
			int foundD = 0;
			while (true)
			{
				int pn = n * (3 * n - 1) / 2;
				for (int i = 1; i < n; i++)
				{
					int pi = i * (3 * i - 1) / 2;
					if (checkP(pn + pi) && checkP(pn - pi))
					{
						foundD = pn - pi;
						break;
					}
				}
				n++;
				if (foundD != 0)
				{
					break;
				}
			}
			return foundD;
		}

		private static dynamic Problem43()
		{
			long sum = 0;
			var posDiv = new List<int>() { 1, 1, 2, 3, 5, 7, 11, 13 };

			Action<List<int>, int, int> searchNum = null;
			searchNum = (List<int> digits, int num, int pos) =>
			{
				if (pos == 1)
				{
					if (!digits.Contains(0))
					{
						return;
					}
					for (int i = 0; i < 10; i++)
					{
						if (!digits.Contains(i))
						{
							sum += long.Parse(i.ToString() + string.Join("", digits.Select(d => d.ToString())));
							break;
						}
					}
				}
				else
				{
					for (int i = 0; i < 10; i++)
					{
						if (!digits.Contains(i))
						{
							var newnum = i * 100 + num / 10;
							if (newnum % posDiv[pos] == 0)
							{
								digits.Insert(0, i);
								searchNum(digits, newnum, pos - 1);
								digits.Remove(i);
							}
						}
					}
				}
			};

			var d17 = 17 * 6;
			while (d17 < 1000)
			{
				List<int> dig = new List<int>();
				var d17_copy = d17;
				while (d17_copy > 0)
				{
					if (dig.Contains(d17_copy % 10))
					{
						break;
					}
					dig.Insert(0, d17_copy % 10);
					d17_copy /= 10;
				}
				if (dig.Count < 3)
				{
					d17 += 17;
					continue;
				}
				searchNum(dig, d17, 7);
				d17 += 17;
			}

			return sum;
		}

		private static dynamic Problem41()
		{
			var numbers = new List<int>();

			Action<int, Dictionary<int, bool>, int> putNumProc = null;
			putNumProc = (int num, Dictionary<int, bool> used, int length) =>
			{
				if (num.ToString().Length == length)
				{
					numbers.Add(num);
					return;
				}
				for (int i = 1; i <= length; i++)
				{
					if (used.ContainsKey(i))
					{
						continue;
					}
					used.Add(i, true);
					var newnum = num == 0 ? i : num * 10 + i;
					putNumProc(newnum, used, length);
					used.Remove(i);
				}
			};

			var max = 0;
			for (int i = 2; i <= 9; i++)
			{
				numbers.Clear();
				putNumProc(0, new Dictionary<int, bool>(), i);
				foreach (var nm in numbers)
				{
					var isprime = true;
					for (int j = 2; j < Math.Floor(Math.Sqrt(nm)); j++)
					{
						if (nm % j == 0)
						{
							isprime = false;
							break;
						}
					}
					if (isprime && nm > max)
					{
						max = nm;
					}
				}
			}
			return max;
		}

		private static dynamic Problem39()
		{
			var phash = new Dictionary<int, int>();
			for (int a = 1; a < 1000; a++)
			{
				for (int b = a + 1; b < 1000 - a; b++)
				{
					var c = Math.Sqrt(a * a + b * b);
					var p = a + b + (int)c;
					if (Math.Floor(c) == c && c > b && p <= 1000)
					{
						if (!phash.ContainsKey(p))
						{
							phash.Add(p, 0);
						}
						phash[p]++;
					}
				}
			}
			var max = 0;
			var maxp = 0;
			foreach (var key in phash.Keys)
			{
				if (phash[key] > max)
				{
					max = phash[key];
					maxp = key;
				}
			}
			return maxp;
		}

		private static dynamic Problem38()
		{
			string num = "";
			var numbers = new Dictionary<int, bool>();
			for (int i = 9876; i >= 9123; i--)
			{
				var ispan = true;
				var pandigital = i.ToString() + (i * 2).ToString();
				numbers.Clear();
				for (int j = 0; j < pandigital.Length; j++)
				{
					var number = int.Parse(pandigital[j] + "");
					if (number == 0 || numbers.ContainsKey(number))
					{
						ispan = false;
						break;
					}
					numbers.Add(number, true);
				}
				if (ispan)
				{
					num = pandigital;
					break;
				}
			}
			return num;
		}

		private static dynamic Problem37()
		{
			var trPrimesList = new List<long>();
			var primes = Misc.esieve(100000);
			Func<long, bool> isTruncPrime = (long num) =>
			{
				if (Misc.isPrime(num, primes))
				{
					var digits = new List<long>();
					long num2 = num / 10;
					digits.Insert(0, num % 10);
					while (num2 > 0)
					{
						if (!Misc.isPrime(num2, primes))
						{
							return false;
						}
						digits.Insert(0, num2 % 10);
						num2 /= 10;
					}
					digits.RemoveAt(0);
					while (digits.Count > 0)
					{
						if (!Misc.isPrime(long.Parse(string.Join("", digits)), primes))
						{
							return false;
						}
						digits.RemoveAt(0);
					}
					return true;
				}
				return false;
			};

			Action<long> checkPrime = null;
			checkPrime = (long num) =>
			{
				if (num.ToString().Length > 1 && isTruncPrime(num))
				{
					trPrimesList.Add(num);
				}
				if (Misc.isPrime(num, primes))
				{
					for (int i = 1; i < 10; i += 2)
					{
						checkPrime(num * 10 + i);
					}
				}
			};
			for (int j = 1; j < 10; j++)
			{
				checkPrime(j);
			}

			long sum = 0;
			for (int j = 0; j < trPrimesList.Count; j++)
			{
				sum += trPrimesList[j];
				if (j == 10)
				{
					break;
				}
			}
			return sum;
		}

		private static dynamic Problem37_2()
		{
			Func<int, bool> IsPrime = (int num) =>
			{
				for (int i = 2; i <= Math.Sqrt(num); i++)
				{
					if (num % i == 0)
					{
						return false;
					}
				}
				return true;
			};

			int result = 0;
			int count = 0;

			List<int> searchList = new List<int>();
			searchList.Add(3);
			searchList.Add(7);

			int[] appends = { 1, 2, 3, 5, 7, 9 };

			var trPrimeList = new List<int>();

			while (count < 11)
			{

				int primeCandidate = searchList[0];
				searchList.RemoveAt(0);

				if (IsPrime(primeCandidate))
				{
					bool isTruncablePrime = true;
					int n = primeCandidate;
					int multiplier = 1;

					//Check right trunacatability
					while (n > 0)
					{
						isTruncablePrime = IsPrime(n) && isTruncablePrime;
						n /= 10;
						multiplier *= 10;

					}

					//Add to the result if a prime is found
					if (isTruncablePrime && primeCandidate > 10)
					{
						trPrimeList.Add(primeCandidate);
						result += primeCandidate;
						count++;
					}

					//Generate new candidates                    
					for (int i = 0; i < appends.Length; i++)
					{
						searchList.Add(multiplier * appends[i] + primeCandidate);
					}
				}
			}

			return result;
		}

		private static dynamic Problem36()
		{
			Func<int, bool, int> getPolindrom = (int num, bool center) =>
			{
				var num2 = num;
				while (num2 > 0)
				{
					if (center)
					{
						center = false;
						num2 /= 10;
						continue;
					}
					num = num * 10 + (num2 % 10);
					num2 /= 10;
				}
				return num;
			};

			Func<int, bool> checkPolindrom = (int num) =>
			{
				var digits = new List<int>();
				var digits_reverse = new List<int>();
				while (num > 0)
				{
					digits.Add(num % 2);
					digits_reverse.Insert(0, num % 2);
					num /= 2;
				}
				if (digits[0] == 0 || digits[digits.Count - 1] == 0)
				{
					return false;
				}
				for (int i = 0; i < digits.Count; i++)
				{
					if (digits[i] != digits_reverse[i])
					{
						return false;
					}
				}
				return true;
			};

			var sum = 0;
			for (int i = 1; i < 1000; i++)
			{
				var pol1 = getPolindrom(i, true);
				sum += (checkPolindrom(pol1) ? pol1 : 0);
				var pol2 = getPolindrom(i, false);
				sum += (checkPolindrom(pol2) ? pol2 : 0);
			}
			return sum;
		}

		private static dynamic Problem35()
		{
			var primes = Misc.esieve(1000000);
			var circPrimes = new List<long>();
			var circPrimesCount = 0;
			foreach (var prime in primes)
			{
				var primeValue = prime;
				var primeNums = new List<long>();
				var primeValueLength = 0;
				while (primeValue > 0)
				{
					primeNums.Insert(0, primeValue % 10);
					primeValue = primeValue / 10;
					primeValueLength++;
				}
				var iscirc = true;
				for (int k = 0; k < primeValueLength; k++)
				{
					var circCandidate = int.Parse(string.Join("", primeNums.Select(pn => pn.ToString())));
					if (!primes.Contains(circCandidate))
					{
						iscirc = false;
						break;
					}
					var last = primeNums[primeNums.Count - 1];
					primeNums.RemoveAt(primeNums.Count - 1);
					primeNums.Insert(0, last);
				}
				if (iscirc)
				{
					circPrimes.Add(prime);
					circPrimesCount++;
				}
			}
			return circPrimesCount;
		}

		private static dynamic Problem34()
		{
			var fact = new Dictionary<int, int>();
			var num = 1;
			fact.Add(0, 1);
			for (int i = 0; i < 9; i++)
			{
				fact.Add(i + 1, num);
				num *= (i + 2);
			}
			var allsum = 0;
			for (int i = 3; i <= fact[9] * 7; i++)
			{
				var k = i;
				var sum = 0;
				while (k > 0)
				{
					sum += fact[k % 10];
					k /= 10;
				}
				if (sum == i)
				{
					allsum += i;
				}
			}
			return allsum;
		}

		private static dynamic Problem33()
		{
			//(i*10+i2) / (j*10+j2) = i/j or i/j2 or i2/j or i2/j2
			int denprod = 1;
			int numprod = 1;
			int denprodcount = 0;
			for (int i = 1; i < 10; i++)
			{
				for (int i2 = 1; i2 < 10; i2++)
				{
					for (int j = i; j < 10; j++)
					{
						for (int j2 = 1; j2 < 10; j2++)
						{
							if (i * 10 + i2 >= j * 10 + j2)
							{
								continue;
							}
							int nom = i * 10 + i2;
							int den = j * 10 + j2;
							if (i < j && i2 == j2 && nom * j == den * i)
							{
								numprod *= i;
								denprod *= j;
								denprodcount++;
							}
							else if (i < j2 && i2 == j && nom * j2 == den * i)
							{
								numprod *= i;
								denprod *= j2;
								denprodcount++;
							}
							else if (i2 < j && i == j2 && nom * j == den * i2)
							{
								numprod *= i2;
								denprod *= j;
								denprodcount++;
							}
							else if (i2 < j2 && i == j && nom * j2 == den * i2)
							{
								numprod *= i2;
								denprod *= j2;
								denprodcount++;
							}
						}
					}
				}
			}

			denprod /= (int)Misc.gcd(numprod, denprod);
			return denprod;
		}

		private static dynamic Problem32()
		{
			long sum = 0;
			Dictionary<string, bool> used = new Dictionary<string, bool>();
			Dictionary<int, bool> used_prod = new Dictionary<int, bool>();
			Dictionary<int, bool> nums = new Dictionary<int, bool>();
			for (int i = 12; i < 1000000; i++)
			{
				nums = new Dictionary<int, bool>();
				int k = i;
				bool err = false;
				while (k > 0)
				{
					if (k % 10 == 0)
					{
						err = true;
						break;
					}
					if (nums.ContainsKey(k % 10))
					{
						err = true;
						break;
					}
					nums.Add(k % 10, true);
					k = k / 10;
				}
				if (err)
				{
					continue;
				}
				var nums_arr = nums.Keys.ToArray();
				for (int j = 1; j < nums_arr.Length; j++)
				{
					var nums_add = new Dictionary<int, bool>();
					var k1 = nums_arr[0];
					for (int j1 = 1; j1 < j; j1++)
					{
						k1 = k1 * 10 + nums_arr[j1];
					}
					var k2 = nums_arr[j];
					for (int j1 = j + 1; j1 < nums_arr.Length; j1++)
					{
						k2 = k2 * 10 + nums_arr[j1];
					}
					var k3 = k1 * k2;
					if (used_prod.ContainsKey(k3))
					{
						continue;
					}
					var k3_copy = k3;
					var err2 = false;
					while (k3_copy > 0)
					{
						if (k3_copy % 10 == 0)
						{
							err2 = true;
							break;
						}
						if (nums.ContainsKey(k3_copy % 10) || nums_add.ContainsKey(k3_copy % 10))
						{
							err2 = true;
							break;
						}
						nums_add.Add(k3_copy % 10, true);
						k3_copy = k3_copy / 10;
					}
					if (err2)
					{
						continue;
					}
					if (nums.Keys.Count + nums_add.Count != 9)
					{
						continue;
					}
					sum += k3;
					used_prod.Add(k3, true);
				}
			}
			return sum;
		}

		[DynamicProgrammingSolution]
		private static dynamic Problem31()
		{
			int target = 200;
			int[] coinSizes = { 1, 2, 5, 10, 20, 50, 100, 200 };
			int[] ways = new int[target + 1];
			ways[0] = 1;

			for (int i = 0; i < coinSizes.Length; i++)
			{
				for (int j = coinSizes[i]; j <= target; j++)
				{
					ways[j] += ways[j - coinSizes[i]];
				}
			}
			return ways[ways.Length - 1];
		}

		private static dynamic Problem30()
		{
			var pows = new Dictionary<int, int>();
			pows.Add(0, 0);
			pows.Add(1, 1);
			for (int i = 2; i < 10; i++)
			{
				pows.Add(i, (int)Math.Pow(i, 5));
			}
			var allsum = 0;
			for (int i = 2; i < pows[9] * 6; i++)
			{
				var k = i;
				var sum = 0;
				while (k > 0)
				{
					sum += pows[k % 10];
					k /= 10;
				}
				if (sum == i)
				{
					allsum += i;
				}
			}
			return allsum;
		}

		private static dynamic Problem29()
		{
			//brute
			Func<int> brute = () =>
			{
				var used = new HashSet<BigInteger>();
				for (int i = 2; i <= 100; i++)
				{
					for (int j = 2; j <= 100; j++)
					{
						used.Add(BigInteger.Pow(i, j));
					}
				}
				return used.Count;
			};
			return brute();
		}

		private static dynamic Problem28()
		{
			int k = 1001 * 1001;
			int step = 1000;
			int sum = 1;
			while (k > 1)
			{
				sum += k + (k - step) + (k - 2 * step) + (k - 3 * step);
				k -= 4 * step;
				step -= 2;
			}
			return sum;
		}

		private static dynamic Problem27()
		{
			const int limit = 10000000;

			HashSet<long> primes = Misc.esieve(limit);

			long maxlen = 0;
			int maxlen_prod = 0;
			for (int a = -999; a < 1000; a++)
			{
				for (int b = -999; b < 1000; b++)
				{
					int n = 0;
					while (primes.Contains(n * n + a * n + b))
					{
						n++;
					}
					if (maxlen == 0 || n > maxlen)
					{
						maxlen = n;
						maxlen_prod = a * b;
					}
				}
			}
			return maxlen_prod;
		}

		private static dynamic Problem26()
		{
			int sequenceLength = 0;
			for (int i = 1000; i > 1; i--)
			{
				if (sequenceLength >= i)
				{
					break;
				}
				int[] foundRemainders = new int[i];
				int value = 1;
				int position = 0;
				while (foundRemainders[value] == 0 && value != 0)
				{
					foundRemainders[value] = position;
					value *= 10;
					value %= i;
					position++;
				}
				if (position - foundRemainders[value] > sequenceLength)
				{
					sequenceLength = position - foundRemainders[value];
				}
			}
			return sequenceLength;
		}

		private static dynamic Problem25()
		{
			Func<List<int>, List<int>, int, List<int>> sum = null;
			sum = (List<int> num1, List<int> num2, int num2shift) =>
			{
				List<int> res = new List<int>();
				for (int i = 0; i < num2shift; i++)
				{
					num2.Insert(0, 0);
				}
				var newnum = 0;
				var remain = 0;
				for (int i = 0; i < Math.Max(num1.Count, num2.Count); i++)
				{
					newnum = ((i < num1.Count ? num1[i] : 0) + (i < num2.Count ? num2[i] : 0) + remain) % 10;
					res.Add(newnum);
					remain = ((i < num1.Count ? num1[i] : 0) + (i < num2.Count ? num2[i] : 0) + remain) / 10;
				}
				if (remain > 0)
				{
					res.Add(remain);
				}
				return res;
			};

			long fibnum = 2;
			var fib = new List<int>();
			var prev_num1 = new List<int>() { 1 };
			var prev_num2 = new List<int>() { 1 };
			while (fib.Count < 1000)
			{
				fib = sum(prev_num1, prev_num2, 0);
				fibnum++;
				prev_num1 = prev_num2;
				prev_num2 = fib;
			}
			return fibnum;
		}

		private static dynamic Problem24()
		{
			Func<int, int> Factor = (int fnum) =>
			{
				if (fnum < 1)
				{
					return 0;
				}
				int p = 1;
				for (int j = 1; j <= fnum; j++)
				{
					p *= j;
				}
				return p;
			};


			string permNum = "";
			int remain = 1000000 - 1;

			List<int> numbers = new List<int>() { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
			int N = numbers.Count;

			for (int i = 1; i < N; i++)
			{
				int j = remain / Factor(N - i);
				remain = remain % Factor(N - i);
				permNum = permNum + numbers[j];
				numbers.RemoveAt(j);
				if (remain == 0)
				{
					break;
				}
			}

			for (int i = 0; i < numbers.Count; i++)
			{
				permNum = permNum + numbers[i];
			}

			return int.Parse(permNum);
		}

		private static dynamic Problem23()
		{
			Dictionary<int, int> nums = new Dictionary<int, int>();
			for (int i = 1; i <= 28123; i++)
			{
				var div_sum = 1;
				for (int j = 2; j < i / 2 + 1; j++)
				{
					if (i % j == 0)
						div_sum += j;
				}
				if (div_sum > i)
				{
					nums.Add(i, div_sum);
				}
			}
			Dictionary<int, bool> ab_twosums = new Dictionary<int, bool>();
			foreach (int i in nums.Keys)
			{
				foreach (int j in nums.Keys)
				{
					if (!ab_twosums.ContainsKey(i + j))
					{
						ab_twosums.Add(i + j, true);
					}
				}
			}
			long def_sum = 0;
			for (int i = 1; i <= 28123; i++)
			{
				if (!ab_twosums.ContainsKey(i))
				{
					def_sum += i;
				}
			}
			return def_sum;
		}

		private static dynamic Problem22()
		{
			var chars = new char[] { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
			var chars_dict = new Dictionary<char, int>();
			for (int i = 0; i < chars.Length; i++)
			{
				chars_dict.Add(char.ToUpper(chars[i]), i + 1);
			}

			var data = File.ReadAllText("names.txt");
			var data_split = data.Split(new string[] { "\",\"" }, StringSplitOptions.RemoveEmptyEntries).ToList();
			data_split[0] = data_split[0].TrimStart('\"');
			data_split[data_split.Count - 1] = data_split[data_split.Count - 1].TrimEnd('\"');
			data_split.Sort();

			var allsum = 0;
			for (int i = 0; i < data_split.Count; i++)
			{
				var sum = 0;
				foreach (var ch in data_split[i])
				{
					sum += chars_dict[ch];
				}
				allsum += sum * (i + 1);
			}
			return allsum;
		}

		private static dynamic Problem21()
		{
			Dictionary<int, int> divs = new Dictionary<int, int>();
			divs.Add(1, 1);
			divs.Add(2, 1);
			divs.Add(3, 1);
			Dictionary<int, bool> divs_used = new Dictionary<int, bool>();
			divs_used.Add(1, false);
			divs_used.Add(2, false);
			divs_used.Add(3, false);
			for (int i = 4; i < 10000; i++)
			{
				divs.Add(i, 1);
				divs_used.Add(i, false);
				for (int j = 2; j < i / 2 + 1; j++)
				{
					if (i % j == 0)
					{
						divs[i] += j;
					}
				}
			}
			long sum = 0;
			for (int i = 1; i < 10000; i++)
			{
				if (divs[i] > 0 && divs[i] < 10000 && i != divs[i] && !divs_used[i] && !divs_used[divs[i]] && divs[divs[i]] == i)
				{
					sum += (i + divs[i]);
					divs_used[i] = true;
					divs_used[divs[i]] = true;
				}
			}
			return sum;
		}

		private static dynamic Problem20()
		{
			List<int> nums = new List<int>() { 2 };

			Func<List<int>, int, List<int>> prod = null;
			prod = (List<int> num1, int num2) =>
			{
				List<int> res = new List<int>();
				var newnum = 0;
				var remain = 0;
				for (int i = 0; i < num1.Count; i++)
				{
					newnum = (num1[i] * num2 + remain) % 10;
					res.Add(newnum);
					remain = (num1[i] * num2 + remain) / 10;
				}
				if (remain > 0)
				{
					res.Add(remain);
				}
				return res;
			};

			Func<List<int>, List<int>, int, List<int>> sum = null;
			sum = (List<int> num1, List<int> num2, int num2shift) =>
			{
				List<int> res = new List<int>();
				for (int i = 0; i < num2shift; i++)
				{
					num2.Insert(0, 0);
				}
				var newnum = 0;
				var remain = 0;
				for (int i = 0; i < Math.Max(num1.Count, num2.Count); i++)
				{
					newnum = ((i < num1.Count ? num1[i] : 0) + (i < num2.Count ? num2[i] : 0) + remain) % 10;
					res.Add(newnum);
					remain = ((i < num1.Count ? num1[i] : 0) + (i < num2.Count ? num2[i] : 0) + remain) / 10;
				}
				if (remain > 0)
				{
					res.Add(remain);
				}
				return res;
			};

			for (int i = 3; i < 101; i++)
			{
				var i2 = i;
				var i2pos = 0;
				List<int> sum_local = new List<int>();
				while (i2 > 0)
				{
					var nm = i2 % 10;
					var res = prod(nums, nm);
					sum_local = sum(sum_local, res, i2pos);
					i2 = i2 / 10;
					i2pos++;
				}
				nums = sum_local;
			}
			var sm = 0;
			foreach (var num in nums)
			{
				sm += num;
			}
			return sm;
		}

		private static dynamic Problem19()
		{
			var count = 0;
			var startDate = new DateTime(1901, 1, 1);
			var endDate = new DateTime(2000, 12, 31);
			for (var day = startDate; day <= endDate; day = day.AddDays(1))
			{
				if (day.DayOfWeek == DayOfWeek.Sunday && day.Day == 1)
					count++;
			}
			return count;
		}

		private static dynamic Problem18()
		{
			string data = @"75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23";

			var data_array = data.Split(new string[] { "\r\n" }, StringSplitOptions.None);

			int total = 0;

			Action<int, int, int> search = null;
			search = (int line, int col, int sum) =>
			{
				sum += int.Parse(data_array[line].Split(' ')[col]);
				if (line == data_array.Length - 1)
				{
					if (sum > total)
					{
						total = sum;
					}
				}
				else
				{
					search(line + 1, col, sum);
					search(line + 1, col + 1, sum);
				}
			};

			search(0, 0, 0);

			return total;
		}

		[SolutionInfo(Links = "http://www.mathblog.dk/project-euler-17-letters-in-the-numbers-1-1000/")]
		private static dynamic Problem17()
		{
			return 21124;
		}

		private static dynamic Problem16()
		{
			List<int> nums = new List<int>() { 2 };
			for (int i = 2; i < 1001; i++)
			{
				var remain = 0;
				var newnum = 0;
				for (int j = 0; j < nums.Count; j++)
				{
					newnum = ((nums[j] * 2) % 10) + remain;
					remain = (nums[j] * 2) / 10;
					nums[j] = newnum;
				}
				if (remain > 0)
				{
					nums.Add(remain);
				}
			}
			var sum = 0;
			foreach (var num in nums)
			{
				sum += num;
			}
			return sum;
		}

		private static dynamic Problem15()
		{
			long div = 1;
			for (int i = 1; i <= 10; i++)
			{
				div *= i;
			}
			long count = 1;
			for (int i = 21; i <= 39; i += 2)
			{
				count *= i * 2;
			}
			count /= div;			
			return count;
		}

		private static dynamic Problem14_2()
		{
			long max = 1;
			long maxi = 1;
			for (long i = 999999; i > 0; i--)
			{
				var k = i;
				var len = 1;
				while (k != 1)
				{
					if (k % 2 == 0)
					{
						k = k / 2;
					}
					else
					{
						k = 3 * k + 1;
					}
					len++;
				}
				if (len > max)
				{
					max = len;
					maxi = i;
				}
			}
			return maxi;
		}

		private static dynamic Problem14()
		{
			Dictionary<long, bool> nums = new Dictionary<long, bool>();

			long prevk = 0;
			long maxlen = 0;

			Action<long, long, long> check = null;
			check = (long i, long previ, long len) =>
			{
				if (i >= 1000000)
				{
					len = nums.Count + (nums.ContainsKey(i) ? -1 : 0);
					if (len > maxlen)
					{
						maxlen = len;
						prevk = previ;
					}
				}
				else
				{
					len = nums.Count + (nums.ContainsKey(i) ? 0 : 1);
					if (len > maxlen)
					{
						maxlen = len;
						prevk = i;
					}
				}
			};

			Action<long, long, long> search = null;
			search = (long i, long previ, long len) =>
			{
				if (i >= 1000000)
				{
					check(i, previ, len);
					return;
				}
				previ = i;
				if (i != 1 && (i - 1) % 3 == 0)
				{
					long nexti = (i - 1) / 3;
					if (nexti == 1 || nums.ContainsKey(nexti))
					{
						if (nums.ContainsKey(i * 2))
						{
							check(i * 2, previ, ++len);
						}
						else
						{
							i = i * 2;
							nums.Add(i, true);
							search(i, previ, ++len);
							nums.Remove(i);
						}
					}
					else
					{
						if (nums.ContainsKey(nexti))
						{
							check(nexti, previ, ++len);
						}
						else if (nexti % 2 == 1)
						{
							nums.Add(nexti, true);
							search(nexti, previ, ++len);
							nums.Remove(nexti);
						}

						if (nums.ContainsKey(i * 2))
						{
							check(i * 2, previ, ++len);
						}
						else
						{
							i = i * 2;
							nums.Add(i, true);
							search(i, previ, ++len);
							nums.Remove(i);
						}
					}
				}
				else
				{
					if (nums.ContainsKey(i * 2))
					{
						check(i * 2, previ, ++len);
					}
					else
					{
						i = i * 2;
						nums.Add(i, true);
						search(i, previ, ++len);
						nums.Remove(i);
					}
				}
			};

			long k = 1;
			nums.Add(k, true);
			search(1, 0, 1);

			return prevk;
		}

		private static dynamic Problem13()
		{
			#region data

			string data = @"37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
23067588207539346171171980310421047513778063246676
89261670696623633820136378418383684178734361726757
28112879812849979408065481931592621691275889832738
44274228917432520321923589422876796487670272189318
47451445736001306439091167216856844588711603153276
70386486105843025439939619828917593665686757934951
62176457141856560629502157223196586755079324193331
64906352462741904929101432445813822663347944758178
92575867718337217661963751590579239728245598838407
58203565325359399008402633568948830189458628227828
80181199384826282014278194139940567587151170094390
35398664372827112653829987240784473053190104293586
86515506006295864861532075273371959191420517255829
71693888707715466499115593487603532921714970056938
54370070576826684624621495650076471787294438377604
53282654108756828443191190634694037855217779295145
36123272525000296071075082563815656710885258350721
45876576172410976447339110607218265236877223636045
17423706905851860660448207621209813287860733969412
81142660418086830619328460811191061556940512689692
51934325451728388641918047049293215058642563049483
62467221648435076201727918039944693004732956340691
15732444386908125794514089057706229429197107928209
55037687525678773091862540744969844508330393682126
18336384825330154686196124348767681297534375946515
80386287592878490201521685554828717201219257766954
78182833757993103614740356856449095527097864797581
16726320100436897842553539920931837441497806860984
48403098129077791799088218795327364475675590848030
87086987551392711854517078544161852424320693150332
59959406895756536782107074926966537676326235447210
69793950679652694742597709739166693763042633987085
41052684708299085211399427365734116182760315001271
65378607361501080857009149939512557028198746004375
35829035317434717326932123578154982629742552737307
94953759765105305946966067683156574377167401875275
88902802571733229619176668713819931811048770190271
25267680276078003013678680992525463401061632866526
36270218540497705585629946580636237993140746255962
24074486908231174977792365466257246923322810917141
91430288197103288597806669760892938638285025333403
34413065578016127815921815005561868836468420090470
23053081172816430487623791969842487255036638784583
11487696932154902810424020138335124462181441773470
63783299490636259666498587618221225225512486764533
67720186971698544312419572409913959008952310058822
95548255300263520781532296796249481641953868218774
76085327132285723110424803456124867697064507995236
37774242535411291684276865538926205024910326572967
23701913275725675285653248258265463092207058596522
29798860272258331913126375147341994889534765745501
18495701454879288984856827726077713721403798879715
38298203783031473527721580348144513491373226651381
34829543829199918180278916522431027392251122869539
40957953066405232632538044100059654939159879593635
29746152185502371307642255121183693803580388584903
41698116222072977186158236678424689157993532961922
62467957194401269043877107275048102390895523597457
23189706772547915061505504953922979530901129967519
86188088225875314529584099251203829009407770775672
11306739708304724483816533873502340845647058077308
82959174767140363198008187129011875491310547126581
97623331044818386269515456334926366572897563400500
42846280183517070527831839425882145521227251250327
55121603546981200581762165212827652751691296897789
32238195734329339946437501907836945765883352399886
75506164965184775180738168837861091527357929701337
62177842752192623401942399639168044983993173312731
32924185707147349566916674687634660915035914677504
99518671430235219628894890102423325116913619626622
73267460800591547471830798392868535206946944540724
76841822524674417161514036427982273348055556214818
97142617910342598647204516893989422179826088076852
87783646182799346313767754307809363333018982642090
10848802521674670883215120185883543223812876952786
71329612474782464538636993009049310363619763878039
62184073572399794223406235393808339651327408011116
66627891981488087797941876876144230030984490851411
60661826293682836764744779239180335110989069790714
85786944089552990653640447425576083659976645795096
66024396409905389607120198219976047599490197230297
64913982680032973156037120041377903785566085089252
16730939319872750275468906903707539413042652315011
94809377245048795150954100921645863754710598436791
78639167021187492431995700641917969777599028300699
15368713711936614952811305876380278410754449733078
40789923115535562561142322423255033685442488917353
44889911501440648020369068063960672322193204149535
41503128880339536053299340368006977710650566631954
81234880673210146739058568557934581403627822703280
82616570773948327592232845941706525094512325230608
22918802058777319719839450180888072429661980811197
77158542502016545090413245809786882778948721859617
72107838435069186155435662884062257473692284509516
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690";

			#endregion

			Func<string, string, string> sum = (string num1, string num2) =>
			{
				var ost = 0;
				var newnum = new StringBuilder();
				for (int i = 0; i < Math.Max(num1.Length, num2.Length); i++)
				{
					var digit1 = i < num1.Length ? int.Parse(num1[i] + "") : 0;
					var digit2 = i < num2.Length ? int.Parse(num2[i] + "") : 0;
					var n = (digit1 + digit2 + ost) % 10;
					newnum.Append(n.ToString());
					ost = (digit1 + digit2 + ost) / 10;
				}
				if (ost > 0)
				{
					newnum.Append(ost.ToString());
				}
				return newnum.ToString();
			};

			var data_numbers = data.Split(new string[] { "\r\n" }, StringSplitOptions.RemoveEmptyEntries);
			var all_sum = "";
			foreach (var data_number in data_numbers)
			{
				all_sum = sum(all_sum, string.Join("", data_number.Reverse().ToArray()));
			}
			long all_sum_num = 0;
			for (int j = all_sum.Length - 1; j > all_sum.Length - 1 - 10; j--)
			{
				all_sum_num = all_sum_num * 10 + int.Parse(all_sum[j] + "");
			}
			return all_sum_num;
		}

		private static dynamic Problem12()
		{
			long sum = 0;
			long divisors = 0;
			long num = 0;
			for (int i = 1; i < 100000; i++)
			{
				sum += i;
				divisors = 0;
				for (int j = 1; j < Math.Floor(Math.Sqrt(sum)); j++)
				{
					if (sum % j == 0)
					{
						divisors += 2;
					}
				}
				if (divisors > 499)
				{
					num = i;
					break;
				}
			}
			return num;
		}

		private static dynamic Problem11_2()
		{
			var data = @"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
						49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
						81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
						52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
						22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
						24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
						32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
						67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
						24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
						21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
						78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
						16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
						86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
						19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
						04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
						88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
						04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
						20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
						20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
						01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48";
			var dataArray = data.Replace("\r\n\t\t\t\t\t\t", " ").Split(' ');

			var dxList = new int[8] { 0, 1, 1, 0, -1, -1, -1, 1 };
			var dyList = new int[8] { 1, 0, 1, -1, 0, -1, 1, -1 };

			var max = 0;

			Func<int, int, int> getPointValue = (int x, int y) =>
			{
				if (x < 0 || x >= 20 || y < 0 || y >= 20)
				{
					return 0;
				}
				return int.Parse(dataArray[x * 20 + y]);
			};

			Action<int, int, int, int> checkPoint = (int x, int y, int dx, int dy) =>
			{
				var prod = getPointValue(x, y) * getPointValue(x + dx, y + dy) * getPointValue(x + 2 * dx, y + 2 * dy) * getPointValue(x + 3 * dx, y + 3 * dy);
				if (prod > max)
				{
					max = prod;
				}
			};

			for (int i = 0; i < 20; i++)
			{
				for (int j = 0; j < 20; j++)
				{
					for (int j2 = 0; j2 < dxList.Length; j2++)
					{
						checkPoint(i, j, dxList[j2], dyList[j2]);
					}
				}
			}
			return max;
		}

		private static dynamic Problem11()
		{
			var data = @"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
						49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
						81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
						52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
						22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
						24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
						32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
						67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
						24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
						21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
						78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
						16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
						86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
						19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
						04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
						88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
						04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
						20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
						20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
						01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48";
			var dataArray = data.Replace("\r\n\t\t\t\t\t\t", " ").Split(' ');

			long max = 0;
			var dx = new int[6] { 0, 1, 1, 0, -1, -1 };
			var dy = new int[6] { 1, 0, 1, -1, 0, -1 };

			Action<dynamic, List<dynamic>> search = null;
			search = (dynamic crpoint, List<dynamic> points) =>
			{
				if (points.Count == 4)
				{
					long prod = 1;
					foreach (var p in points)
					{
						prod *= int.Parse(dataArray[p.x * 20 + p.y] + "");
					}
					if (prod > max)
					{
						max = prod;
					}
				}
				else
				{
					for (int k = 0; k < dx.Length; k++)
					{
						dynamic newp = new { x = crpoint.x + dx[k], y = crpoint.y + dy[k] };
						if (newp.x < 0 || newp.x >= 20 || newp.y < 0 || newp.y >= 20)
						{
							continue;
						}
						var dbl = false;
						foreach (var p in points)
						{
							if (p.x == newp.x && p.y == newp.y)
							{
								dbl = true;
								break;
							}
						}
						if (dbl)
						{
							continue;
						}
						points.Add(newp);
						search(newp, points);
						points.Remove(newp);
					}
				}
			};

			var pointsGlobal = new List<dynamic>();
			for (int i = 0; i < 20; i++)
			{
				for (int j = 0; j < 20; j++)
				{
					dynamic newp = new { x = i, y = j };
					pointsGlobal.Add(newp);
					search(newp, pointsGlobal);
					pointsGlobal.Remove(newp);
				}
			}
			return max;
		}
	}
}
